【剑指Offer】面试题39：数组中出现次数超过一半的数字

发表于 | 分类于 | 阅读次数:

题目：数组中有一个数字出现的次数超过了数组长度的一半，请找出这个数字。例如，输入一个长度为 9 的数组 {1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数组 2 在数组中出现了 5 次，超出数组长度的一半，因此输出 2。

思路 1：排序

最直接的思路就是：将这个数组排序，排序完之后数组就是有序的了，然后直接访问这个数组的中位数，也就是索引为 $\frac{n}{2}$ 的元素，就是我们寻找的数字。但是这个算法的时间复杂度比较高，排序所需要的时间复杂度是 O(nlogn)，并且需要修改输入的数组。这个算法能够在面试官刚提出题目之后快速的答上来，可以体现自己思维比较敏捷，但是需要能够提出时间复杂度更小的算法才能够获得面试官的青睐。

思路 2：Partition

从上一个思路，我们可以得到启发，实际上我们就是要找到排好序之后索引为 $\frac{n}{2}$ 的元素，也就是中位数。那我们一定要把整个数组完全的排好序吗？这不一定，这个算法的灵感来源于快速排序。

算法思路就是：

  • 我们先选择数组中的一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字放置于它的左边，比选中的数字大的数字放置于它的右边
  • 判断选中的数字的索引是否等于 $\frac{n}{2}$。如果相等，这个数字就是我们寻找的数字，也就是中位数；如果大于 $\frac{n}{2}$，那么中位数在它的左边，对左边的部分递归的查找；如果小于 $\frac{n}{2}$，那么中位数在它的右边，对右边的部分递归的查找

这样做不需要对整个数组排序，只需要局部的排序就能够达到目的，算法的时间复杂度是 O(n)。但是缺点在于依然需要修改输入的数组。

思路 3：阵地攻守

输入的数组中有一个数字超过了数组长度的一半，也就是说，这个数字的个数比其他所有数字的个数都要多。基于这个特点，我们便产生了一个不需要修改数组的思路：阵地攻守。简而言之，也就是，遇到敌人同归于尽，遇到同伴数量增加。

思路是：我们使用一个临时变量存储数字，另一个临时变量存储次数。从头到尾的遍历数组，如果当前数字与数字变量（也就是之前保存的数字）中的数字相同，次数变量就加 1，否则就减 1；如果次数为 0，那么我们需要将数字变量赋值为当前数字，并把次数变量赋值为 1。由于我们要寻找的数字比其他数字的个数都要多，因此最后在数字变量中存储并且次数变量大于 0 的数字就是我们要寻找的数字。

这个算法只需要从头到尾的遍历一遍数组，因此算法的时间复杂度是 O(n)，并且不需要修改输入的数组。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public int MoreThanHalfNum_Solution(int[] array) {
        // 特殊输入的检查
        if (array == null || array.length == 0)
            return 0;
        if (array.length == 1)
            return array[0];

        int count = 1;
        int num = array[0];

        // 阵地攻守的思想：遇到敌人同归于尽，遇到同伴数量增加
        for (int i = 1; i < array.length; i++) {
            if (count == 0) {
                num = array[i];
                count++;
            } else {
                if (num == array[i])
                    count++;
                else
                    count--;
            }
        }

        // 检查数组确实有一个数字出现的次数超过数组长度的一半
        return checkMoreThanHalf(array, num) ? num : 0;
    }

    private boolean checkMoreThanHalf(int[] a, int n) {
        int count = 0;
        for (int i = 0; i < a.length; i++)
            if (n == a[i])
                count++;
        return count > (a.length / 2);
    }
}