Sword finger offer note: T39. Numbers that appear more than half of the time in the array

T39. A number that appears more than half the times in an array

There is a number in an array that appears more than half the length of the array , Please find out the number .

You can assume that the array is not empty , And there are always many elements in a given array .

Example 1:

Input : [1, 2, 3, 2, 2, 2, 5, 4, 2]
Output : 2

Limit ：

1 <= The length of the array <= 50000

Ideas

Use the technique of dichotomy , The last number in the middle is this number

solution 1 Direct sort

class Solution {
    
    public int majorityElement(int[] nums) {
    
        Arrays.sort(nums);
        return nums[nums.length>>1];
    }
}

Execution time ：2 ms, In all Java Defeated in submission **60.35%** Users of

Memory consumption ：43.9 MB, In all Java Defeated in submission **9.12%** Users of

solution 2 Moore voted ( clever )

class Solution {
    
    public int majorityElement(int[] nums) {
    
        int n=0, count=0;
        for(int num:nums){
    
            if(count==0){
    
                n = num;
            }
             if(num ==n){
    
                count++;
            }else count--;
        }
        return n;
    }
}

Execution time ：1 ms, In all Java Defeated in submission **99.97%** Users of

Memory consumption ：41.5 MB, In all Java Defeated in submission **87.71%** Users of

Time complexity ：O(n), Spatial complexity ：O(1)