【剑指offer】数组中出现次数超过一半的数字

注意：数组中有没有次数超过一半的数字。
方法1
运用数组的特性：数组中有一个数字的个数超过了数组长度的一半，那么这个数字一定是数组中的中位数。
基于快排算法 --> 求数组总第k大的数字 O(n)

public class Solution {

    public int Partition(int[] array, int l, int r) {
        int x = array[l];
        while (l < r) {
            while (l < r && array[r] >= x) r--;
            array[l] = array[r];
            while (l < r && array[l] <= x) l++;
            array[r] = array[l];
        }
        array[l] = x;
        return l;
    }

    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null) {
            return 0;
        }
        int mid = array.length >> 1;
        int l = 0, r = array.length - 1, index = 0;
        while (index != mid) {
            index = Partition(array, l, r);
            if (index > mid) {
                r = index - 1;
            } else if (index < mid) {
                l = index + 1;
            }
        }
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == array[index]) {
                count++;
            }
        }
        return count > mid ? array[index] : 0;
    }
}

方法2
遍历数组时保存两个值：一个是数字中的一个数字，另一个是次数。

public class Solution {
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null) {
            return 0;
        }
        int count = 0, num = -1;
        for (int i = 0; i < array.length; i++) {
            if (count == 0) {
                count++;
                num = array[i];
                continue;
            }
            if (array[i] == array[i - 1]) {
                count++;
            } else {
                count--;
            }
        }
        count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num) {
                count++;
            }
        }
        return count > array.length / 2 ? num : 0;
    }
}