169. Majority Element

问题描述

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

解题思路

类似于堆栈，若当前元素与majority元素相等时，计数器count加1，若不等，则计数器减一。当计数器减为零时，更换majority元素。下边给出多种解法

int majorityElement(vector<int>& nums) {
        int max = nums[0];
        int count = 1 ;
        for(int i = 0; i<nums.size();i++){
            if(nums[i]==max){
                count++;
            }else{
                count--;
                if(count <1){
                    max = nums[i];
                    count++;
                }
            }
        }
        return max;
    }

---

Hash Table

int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts; 
        int n = nums.size();
        for (int i = 0; i < n; i++)
            if (++counts[nums[i]] > n / 2)
                return nums[i];
    }

---

sort

因为majority的出现次数超过n/2次，所以当nums排好序后，位于中间的元素即为所求元素

 int majorityElement(vector<int>& nums) {
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        return nums[nums.size() / 2];
    } 

---

Randomization

随机化，有着很好的运行速度

int majorityElement(vector<int>& nums) {
        int n = nums.size();
        srand(unsigned(time(NULL)));
        while (true) {
            int idx = rand() % n;
            int candidate = nums[idx];
            int counts = 0; 
            for (int i = 0; i < n; i++)
                if (nums[i] == candidate)
                    counts++; 
            if (counts > n / 2) return candidate;
        }
    }