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

题目分析

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
其中解法一用到了快速排序的 partion 函数。解法二是用到了解决该问题的特殊的方法。

代码

解法一

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null) {
            return 0;
        }
        if(array.length == 0) {
            return 0;
        }
        int start = 0;
        int end = array.length - 1;
        int mid = array.length >> 1;
        int index = partition(array, start, end);
        while(index != mid) {
            if(index < mid) {
                index = partition(array, index + 1, end);
            } else {
                index = partition(array, start, index - 1);
            }
        }
        int res = array[mid];
        int count = 0;
        for(int i = 0; i < array.length; i++) {
            if(array[i] == res) {
                count ++;
            }
        }
        if(count > array.length / 2) {
            return res;
        } else {
            return 0;
        }
    }
    
    public int partition(int[] array, int start, int end) {
        int pivot = array[start];
        while (start < end){
            while (start < end && array[end] >= pivot) --end;
            array[start] = array[end];
            while (start < end && array[start] <= pivot) ++start;
            array[end] = array[start];
        }
        array[start] = pivot;
        return start;
    }
}

解法二

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        // 空指针
        if(array == null) {
            return 0;
        }
        // 空数组
        if(array.length == 0) {
            return 0;
        }
        
        int res = array[0];
        int times = 1;
        
        for(int i = 1; i < array.length; i++) {
            if(array[i] == res) {
                times ++;
            } else if(times == 0) {
                res = array[i];
                times = 1;
            } else {
                times --;
            }
        }
        
        int count = 0;
        for(int i = 0; i < array.length; i++) {
            if(array[i] == res) {
                count ++;
            }
        }
        
        if(count > array.length / 2) {
            return res;
        } else {
            return 0;
        }
    }
}