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

题目

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

思路

思路一

先排序，则次数超过一半的数字一定在数组中间。
可以利用快排的partition方法，获得某随机数字x，将比x小的排到数组左边，比x大的排到数组右边。得到x的位置index，若index比n/2小，则在右数组继续查找；否则在左数组继续查找。直到index=n/2.
时间复杂度O(n)。

思路二

由于某数字次数超过数组一半，即该数字出现的次数比其他数字次数和都多。
因此，我们可以遍历数组，并在此过程中保存两个值，一个是数组中的数字num，一个是次数count。

• 当遍历到某个数字i 时，若num == i，则count++；
• 若num ！= i，则count–；
• 若count==0，则num=i，且count=1
  则，最后一次将count置为1的数字就是目标数字。
  最后，验证一下得到的数字的次数是否超过数组一半。
  时间复杂度O(n)。

这里需要验证一下的原因是，这种方法等于将数组分为两部分，一部分是某数字，一部分是其他数字，不管任何一部分超过一半，都会出现count最后>0。因此对于其他数字超过一半的情况，需要验证。

测试用例

1.功能测试（存在或者不存在超过数组长度一半的数字）
2.特殊测试（null、1个数字）

Java实现

实现二

public class MoreThanHalfNum_Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        int half = array[0];
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (count == 0) {
                half = array[i];
                count++;
            } else if (half == array[i]) {
                count++;
            } else {
                count--;
            }
        }
        if (checkHalf(half, array)) {
            return half;
        }
        return 0;
    }

    public boolean checkHalf(int half, int[] array) {
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == half) {
                count++;
                if (count > array.length >> 1) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,2,4,2,5,2,2};
        MoreThanHalfNum_Solution moreThanHalfNum_solution = new MoreThanHalfNum_Solution();
        int re = moreThanHalfNum_solution.MoreThanHalfNum_Solution(arr);
        System.out.println(re);
    }
}

收获

1、不管是思路一还是思路二，都是O(n)的时间复杂度。
2、思路二是一种跳脱常规思维的思路。可以借鉴。
3、用length>>1代替length/2，速度更快。