LeetCode -- Majority Element

LeetCode -- Majority Element

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.


Credits:
Special thanks to @ts for adding this problem and creating all test cases.

找出出現次數大於數組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();
    	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;
    }
}