字节面试：两道数组面试题，请收下

发表于 3年以前 | 总阅读数：304 次

故事

上周五，一位朋友去字节面试了，面试的时候，被问到两个数组面试题。第一个问题他现场把代码写出来了，但是第二道题，他说了一些思路但是不能满足题目条件，最后，第二道题就失败了。

接下来，我们就好好分析一下到底有多简单有多难。

看题

第一道：如何判断数组中不存在重复的元素，并且时间复杂度为O(n)。存在重复输出"没有重复元素"，不存在输出"存在重复元素"。

第二道：找出数组中元素个数已经超过数组长度一半的，另外，数组中肯定是存在的，要求时间复杂度是 O(n)，空间复杂度是 O(1)。并输出该元素。

题目分析

第一道题分析

int [] arr={1,2,3,5,2};输出"存在重复元素"；

int [] arr={1,2,3,5};输出YES"没有重复元素"；

这里需要注意的是时间复杂即可。

这位同学听到面试官说这道题目的时候，第一反应就是我们Java有一种数据结构叫做Set，Set中就是可以保存不能重复的，然后再联系到HashSet。

最终，他居然想到HashSet的后背就是使用HashMap来实现的。

代码实现

public class ArrayDemo {
    public static void main(String[] args) {
//        int[] a = {1, 2, 3, 4, 5};
        int[] arr = {1, 2, 3, 4, 1};
        isOnlyOne(arr);
    }  
    public static void isOnlyOne(int[] arr) {
        boolean isOnlyOne = true;
        Map<Integer, Integer> d = new HashMap<>(arr.length);
        for (int i = 0; i < arr.length; i++) {
            if (d.containsKey(arr[i])) {
                isOnlyOne = false;
            }
            d.put(arr[i], 1);
        }
        System.out.println(isOnlyOne ? "没有重复元素" : "存在重复元素");
    }
}

面试官的反应

面试官看了上面代码，然后问为什么使用数组的长度去初始化HashMap?这位同学回答的是：这样可以避免不必要的因为扩容导致的性能问题（我猜测此时面试官心里想，小伙子可以的，这问题都考虑进去了）。

面试官又接着问：如果我现在数组长度是20，那么HashMap的初始容量是多少呢？

尴尬了，这位同学直接回答的是20。你认为是多少？嘿嘿，大部分还是知道的，不知道请自行查询。

面试官继续问：HashMap就能满足时间复杂O(n)吗？这位同学直接说的是HashMap的时间复杂度是O(1)，所以能满足时间复杂度为O(n)的问题。这个问题补充一下：我也不知道这位面试官是否认同这位同学的回答，HashMap的时间复杂度理想状态确实O(1)，但是也有可能的值有O(1)、O(logn)、O(n)。

这位同学把这道题是搞定了，但是还是没有获得满分，但也算是搞定这个面试题了。

接着面试官又问了第二道题，下面，我们就来详细分析分析。

第二道题分析

找出数组中出现次数超过数组长度一半的元素。

int [] arr={1,2,2,2,3,3,2};输出2。

但是这里需要注意两个问题：

时间复杂度是 O(n)，空间复杂度是O(1)。

同学看到这道题后，又想到了HashMap，上一道题中，已经说多HashMap的时间复杂度了，那这里时间复杂度是肯定没问题的。

但是再想想空间复杂O(1)，明显不能满足的。于是就没下文了。

下面我们来分析分析这道题。

从问题出发，这并不是某个特定类型的问题。而且既然空间复杂度限定是 O(1)，也就意味着不允许使用任何复杂的数据结构。也就是说，数据结构的优化不可以用，算法思维的优化也不可以用。

面对这类问题，我们只能从问题出发，看还有哪些信息我们没有使用上。题目中有一个重要的信息是，这个出现超过半数的数字一定存在。回想我们上边的解法，它可以找到出现次数最多的数字，但没有使用到“必然超过半数”这个重要的信息。

分析到这里，我们不妨想一下这个场景。

假设现在三国交战，其中 A 国的兵力比 B 国和 C 国的总和还多。那么人们就常常会说，哪怕是 A 国士兵“一个碰一个”地和另外两国打消耗战，都能取得最后的胜利。

说到这里，不知道你有没有一些发现。“一个碰一个”的思想，那就是如果相等则加 1，如果不等则减 1。这样，只需要记录一个当前的缓存元素变量和一个次数统计变量就可以了。

代码实现

public class ArrayDemo {
    public static void main(String[] args) {
        int[] arr = {1,2,2,2,3,3,2};
        moreHalf(arr);
    }
    public static void moreHalf(int[] arr) {
        //初始化变量，结果 result 赋值为 a[0]，
        int result = arr[0];
        //次数 times 为 1。
        int times = 1;
        //接着进入循环体，执行“一个碰一个”
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != result) {
            //如果当前元素与 a[i] 不相等，次数减 1；
                times--;
            } else {
            //如果当前元素与 a[i] 相等，次数加 1。
                times++;
            }
            //当次数降低为 -1 时，则发生了结果跳转。
            if (times == -1) {
                //result 更新为 a[i]，次数重新置为 1。
                times = 1;
                result = arr[i];
            }
        }
        System.out.println(result);
    }
}

最终我们就在 O(n) 的时间复杂度，同时O(1 )的空间复杂度下，找到了结果。