169 Majority Element

Leetcode

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

---

o(n) 的解法，基于 partition ，结果不太理想。

Runtime: 322 ms, faster than 5.05% of Java online submissions for Majority Element.
Memory Usage: 45.5 MB, less than 76.94% of Java online submissions for Majority Element.

每次 partition 后左边的元素都都小于等于中间元素，右边的元素都大于等于中间元素，不断 partition 直到返回中间元素。如果一个元素出现次数超过一半，那么中间元素一定是它。

class Solution {
    public int majorityElement(int[] nums) {
        
        int mid=nums.length >> 1;
        int left=0,right=nums.length-1;
        int index=partition(nums, left, right);
        while(index!=mid){
            if(index<mid){
                left=index+1;
            } else {
                right=index-1;
            }
            index=partition(nums, left, right);
        }
        return nums[index];
    }
    
    private int partition(int[] nums, int begin, int right){
        int left=begin;
        int pivot=nums[begin];
        while(left<right){
            while(left<right && nums[right]>pivot) right--;
            while(left<right && nums[left]<=pivot) left++;
            if(left<right){
                int t=nums[left];
                nums[left]=nums[right];
                nums[right]=t;
            }
        }
        nums[begin]=nums[left];
        nums[left]=pivot;
        return left;
    }
}