LeetCode -- Majority Element

找出出现次数大于数组1/2 长度次的数字。

思路：

本题解法很多：

1.排序后判断第n/2个元素与首元素是否相等

2.哈希表

3.每次移除两个不等的元素

...

第3种方法最快，在实际应用中，哪种方式的时间复杂度都是可以接受的，这里的实现使用了第二种，即借助哈希表来完成统计。

实现代码：

public class Solution {
    public int MajorityElement(int[] nums) {
        if(nums.Length == 0){
    		return 0;
    	}
    	
    	var hash = new Dictionary<int, int>();
    	var max = 1;
    	var maxKey = nums[0];
    	for(var i = 0;i < nums.Length; i++){
    		if(hash.ContainsKey(nums[i])){
    			hash[nums[i]] ++;
    			if(max < hash[nums[i]]){
    				max = hash[nums[i]];
    				maxKey = nums[i];
    			}
    		}
    		else{
    			hash.Add(nums[i],1);
    		}
    	}
    	
    	return maxKey;
    }
}

LeetCode -- Majority Element

原文：http://blog.csdn.net/lan_liang/article/details/48897025