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.

解题思路：

1、用一个map记录每个数的出现的次数。若出现某个数的计数大于n/2，返回该数。

class Solution {
public:
    int majorityElement(vector &num) {
        int len = num.size();
        map count;
        for(int i=0; i len/2){
                return num[i];
            }
        }
        return 0;
    }
};

2、对于一个排序数组来说，若众数存在，众数肯定是中间那个数。

class Solution {
public:
    int majorityElement(vector &num) {
        std::sort(num.begin(), num.end());
        return num[num.size()/2];
    }
};

3、投票算法。可以想成打擂台，台上那个人若输赢次数相同，则下台，最后打败他的人上台。众数肯定是最后的赢家。这个算法用的时间最少了。

class Solution {
public:
    int majorityElement(vector &num) {
        int len = num.size();
        if(len==0){
            return 0;
        }
        int candidate = num[0];
        int count = 1;
        for(int i=1; i
4、位算法。考虑到每个数都可以用32位二进制表示，对每个数的每一位二进制为1的计数，若某个二进制位的计数大于n/2，肯定有众数的贡献。这种办法很新颖，虽然速度比不上投票算法，但是开拓思维嘛。这里说一点，第一种方法中，定义了map count，对于每个新加入的键值，其值默认为0，但是对于int数组类型，每个数组初始化为随机值，因此要用memset函数呀。
class Solution {
public:
    int majorityElement(vector &num) {
        int len = num.size();
        if(len==0){
            return 0;
        }
        int bitCount[32];
        memset(bitCount, 0, 32*sizeof(int));
        for(int i=0; i len/2)         //第i位为1的计数大于一半，肯定有众数的贡献
                result += (int)pow(2, i);
        }
        return result;
    }
};
二次刷题（2015-08-06）
投票算法：
class Solution {
public:
    int majorityElement(vector& nums) {
        int result = 0;
        int count = 0;
        int len = nums.size();
        for(int i=0; i

 
转载请注明： » [LeetCode] Majority Element

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->