39-数组中出现次数超过一半的数字

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

我们可以直接根据题目的意思，统计每个数字出现的次数，然后遍历检查即可。

统计数字次数

我们使用一个HashMap来保存数字的出现次数。

 public int MoreThanHalfNum_Solution(int [] array) {
        if (array == null) {
            return 0;
        }
        Map<Integer, Integer> data = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int ele = array[i];
            if (data.containsKey(ele)) {
                data.put(ele, data.get(ele) + 1);
            }else{
                data.put(ele, 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : data.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            if (value * 2 > array.length) {
                return key;
            }
        }
        return 0;
    }

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

快排思想

当数组中有一个数字的出现次数多于一半时，显然当排序后，数组中间的数字一定是这个数字。

所以我们可以对数组进行排序，然后找到中间的数字，进行检验。

结合快排的思想，我们可以使用partition算法来更快速的找到中间的数字。

partition算法每次都会返回一个位置，此位置将数组一分为二，左侧都小于此位置上的数字，右侧都大于此位置上的数字。

我们首先执行一次partition算法，返回分隔位置K，假定数组的中间位置为M,

1. 如果 K == M,那么这个就是中间位置了，检查。
2. 如果 K > M,说明我们需要在后半部分在继续查找。
3. 如果 K < M,说明我们需要在前半部分继续查找。

partition算法有单边和双边计算，双边计算有两个指针，从左和右同时比较，单边计算是仅从一边遍历比较。

//双边算法 
private int partition(int[] array, int lo, int hi) {
        if (lo >= hi) {
            return lo;
        }
        int pivot = array[lo];
        int i = lo;
        int j = hi + 1;
        while (true) {
            while(array[++i] < pivot){
                if (i == hi) {
                    break;
                }
            }
            while(array[--j] > pivot){
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(array, i, j);
        }
        swap(array, lo, j);
        return i;
    }
//单边算法
  private int partition2(int[] array, int lo, int hi) {
        if (lo >= hi) {
            return lo;
        }
        int pivot = array[lo];
        int mark = lo;
        for (int i = lo + 1; i <= hi; i++) {
            if (array[i] < pivot) {
                mark++;
                swap(array, mark, i);
            }
        }
        swap(array, mark, lo);
        return mark;
    }
//主程序
  public int MoreThanHalfNum_Solution3(int [] array) {
        if (array == null) {
            return 0;
        }
        int hi = array.length - 1;
        int lo = 0;
        int k = partition(array, lo, hi);
        int middle = array.length / 2;
        while (k != middle) {
            if (k < middle) {
                lo = k + 1;
            }else{
                hi = k - 1;
            }
            k = partition(array, lo, hi);
        }
        if (checkMoreThanHalf(array,array[k])) {
            return array[k];
        }
        return 0;
    }