leetcode169——Majority Element （C++），majorityelement

leetcode169——Majority Element （C++），majorityelement

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.

個人博客：http://www.cnblogs.com/wdfwolf3/。

題目比較好理解，在含有n個元素的數組中找出出現次數超過⌊n/2⌋的元素，假設數組不為空而且這個數是一定存在的。

1.moore-voting算法

這個算法就是為解決這個問題誕生的，主要思想就是找出一對不同的元素就去掉它們，最後剩下的一定是所找的元素。

class Solution { public: int majorityElement(vector<int>& nums) { int result=nums[0],count,i; for(i=1,count=1;i<nums.size();i++) { count+=nums[i]==result?1:-1; if(count>nums.size()/2) break; if(count==0) { count=1; result=nums[i+1]; i++; } } return result; } } View Code(16ms)

2.hash

遍歷數組，利用hash方式記錄元素出現的次數，當某個元素次數超過⌊n/2⌋時，即為我們要找的。

class Solution { public: int majorityElement(vector<int>& nums) { unordered_map<int,int> m; int i; for(i=0;i<nums.size();i++) { if(++m[nums[i]]>(nums.size()/2)) return nums[i]; } return nums[0]; } }; View Code(28ms)

3.sorting

對數組進行排序，由於要找的元素超過半數，所以下標n/2的元素一定是它，這裡總數奇偶不影響，可以自己舉例驗證一下。

class Solution {
public:
    int majorityElement(vector<int>& nums) {      //40ms
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

4.randomization

隨機選取數組中的一個數，驗證它是不是超過半數的數字。時間最快，有一半幾率選中，當然最壞的情況比較糟糕，但這不重要，就像快速排序時間復雜度一樣。

class Solution { public: int majorityElement(vector<int>& nums) { srand(unsigned(time(NULL))); int tmp,i,count; while(true) { tmp=nums[rand()%nums.size()]; for(i=0,count=0;i<nums.size();i++) { if(tmp==nums[i]) count++; if(count>nums.size()/2) return tmp; } } } }; View Code(16ms)

5.bit manipulation

就是把數字都作為二進制處理，每個二進制位上的n個bit相加看是否大於n/2，大於的話這一位上是1，小於的話就是0，把32位都這麼處理完就知道結果是多少了。

class Solution { public: int majorityElement(vector<int>& nums) { int i,j,count,major=0; for(i=0;i<32;i++) { for(j=0,count=0;j<nums.size();j++) { if((nums[j]>>i&1)==1) count++; } if(count>nums.size()/2) major+=(1<<i); } return major; } } View Code（40ms）

6.分治

處理這種問題都可以嘗試下分治方法，這道題也可以不過感覺太麻煩，就不寫了。