【LeetCode】169

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.

Solution 1: 使用map计数

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {　　　　//runtime:32ms
 4         map<int, int> nums_count;
 5         vector<int>::iterator iter=nums.begin();
 6         
 7         while(iter!=nums.end()){
 8             ++nums_count[*iter];
 9             iter++;
10         }
11         
12         int n=nums.size();
13         
14         map<int, int>::iterator ite=nums_count.begin();
15         //int max=ite->second;
16         while(ite!=nums_count.end()){
17             if(ite->second>n/2){
18                 return ite->first;
19             }
20             ite++;
21         }
22     }
23 };

Solution 2: 每找出两个不同的element就成对删除，最后可能剩两个元素或一个元素，必定都是所求

 1 class Solution {
 2 public:
 3     int majorityElement(vector<int>& nums) {    //runtime: 20ms
 4         int count=0;
 5         int ret;
 6         for(int i=0;i<nums.size();i++){
 7             if(count==0){
 8                 ret=nums[i];
 9                 count++;
10             }else{
11                 if(nums[i]==ret)
12                     count++;
13                 else
14                     count--;
15             }
16         }
17         return ret;
18     }
19 };

扩展到⌊ n/k ⌋的情况，每k个不同的element进行成对删除