刷题20——面试题39：数组中出现次数超过一半的数字

题目：

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

思路一：基于Partition函数的时间复杂度为O(n)的算法

如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。也就是说，这个数字就是统计学上的中位数，即长度为n的数组中第n/2大的数字。我们有成熟的时间复杂度为O(n)的算法得到数组中任意第k大的数字。

这种算法受快速排序算法的启发。在随机快速排序算法中，我们先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组中的中位数；如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找；如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程。

思路二：根据数组特点找出时间复杂度为O(n)的算法

数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其它所有数字出现次数的和还要多。因此，我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个数字；另一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1.如果次数为0，那么我们需要保存下一个数字，并把次数设为1.由于我们要找的数字出现的次数比其它所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把数字设为1时对应的数字。

python代码如下：

class Solution:
    def moreThanHalfNum(self, nums):
        count =1
        num =nums[0]
        for i in nums[1:]:
            if num ==i:
                count +=1
            else:
                count -=1
                if count ==0:
                    num =i
                    count +=1
        
        sum =0
        for j in nums:
            if j ==num:
                sum +=1
                
        return num if sum>len(nums)//2 else 0

java代码如下：

public int moreThanHalfNum(int[] array){
    if(array ==null)
        return 0;
    int N =array.length;
    int count =0;
    int root =0;
    for(int i=0; i<N; i++){
        if(count==0){
            root =array[i];
            count =1;
        }
        if(array[i] ==root){
            count++;
        }else{
            count--;
        }
    }
    //判断数组中是否存在出现次数大于一半的数字
    if(checkArray(array, root)){
        return root;
    }else{
        return 0;
    }
}

private boolean checkArray(int[] array, int root){
    int N=array.length;
    int num=0;
    for(int i=0; i<N; i++){
        if(array[i] ==root){
            num++;
        }
    }
    if(num*2>N)
        return true;
    else
        return false;
}

更多精彩，关注“咋家”