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

牛客

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

数据范围：n ≤50000，数组中元素的值 0≤val≤10000

要求：空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)

输入描述： 保证数组输入非空，且保证有解

示例1
输入：[1,2,3,2,2,2,5,4,2]
返回值：2

示例2
输入：[3,3,3,3,2,2,2]
返回值：3

示例3
输入：[1]
返回值：1

时间复杂度 o(n) 的方法，基于 partition ，每次 partition 后左边的元素都都小于等于中间元素，右边的元素都大于等于中间元素，不断 partition 直到返回中间元素。如果一个元素出现次数超过一半，那么中间元素一定是它。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int mid=array.length/2;
        int index=partition(array, 0, array.length-1);
        while(index!=mid){
            if(index<mid){
                index=partition(array, index+1, array.length-1);
            } else {
                index=partition(array, 0, index-1);
            }
        }
        return array[mid];
         
    }
     
    private int partition(int[] array, int begin, int end){
        int left=begin, right=end;
        int first=array[begin];
        while(left<right){
            while(left<right && array[right]>first) right--;
            while(left<right && array[left]<=first) left++;
            if(left<right){
                int t=array[left];
                array[left]=array[right];
                array[right]=t;
            }
        }
        array[0]=array[left];
        array[left]=first;
        return left;
    }
}