#169. Majority Element

題目描述

給你一個長度n的整數陣列nums，回傳主要元素(Majority Element)。

主要元素指的是在陣列中出現超過[n/2]次的元素，你可以假設主要元素必定存在於每個整數陣列中。

限制條件

n == nums.length
1 <= n <= 5*10^4
-10^9 <= 陣列元素值 <= 10^9
主要元素必定存在於陣列中。

解題思路

Brute Force

要完成這個問題最直覺的方式就是把所有的數字出現的數量都記錄下來，找出出現最多的數字。因為主要元素必定存在於陣列中，而主要元素的條件是出現次數大於一半的陣列長度，因此我們在途中如果遇上了，就可以直接回傳，節省時間。

public class Solution {
	public int MajorityElement(int[] nums) {
		var ht = new Hashtable();
			for(int i=0;i<nums.Length;i++){
				if(ht.Contains(nums[i])){
					var newVal = (int)ht[nums[i]]+1;
					if(newVal > nums.Length/2) return nums[i];
					ht[nums[i]] = newVal;
				}else{
					ht.Add(nums[i],1);
				}
			}
			int maxV = 0;
			int maxK = Int32.MaxValue;
			foreach(DictionaryEntry kv in ht){
				if((int)kv.Value > maxV){
					maxV = (int)kv.Value;
					maxK = (int)kv.Key;
				}
			}
			return maxK;
	}
}

複雜度分析：

時間複雜度：由於要檢查所有的數字，最差情況下要檢查完所有的陣列，因此時間複雜度為O(n)。
空間複雜度：由於主要元素至少占了n/2的出現次數，所以最差的情況會需要記錄下n/2個不同的數字，因此空間複雜度為O(n)。

Follow-up

你可以讓這個函式的運作時間為線性並且空間複雜度為O(1)嗎?

投票法 Boyer–Moore Majority Vote Algorithm

我們已經知道每個陣列存在主要元素這個前提，而主要元素的數量會大於n/2個陣列，我們可以認為主要元素總數量減去其餘的元素，最後留下來的一定會是主要元素。

舉例來說: 陣列長度為100，主要元素最少會佔據51，而剩下49則是其他元素，那麼每一個主要元素和其他元素抵銷，最後會剩下2個主要元素。

因此可以這樣處理這個問題：

選取一個元素，先假設他是主要元素，在計數器上記錄1。
繼續往後檢查其他元素，如果下一個元素和我們選定的元素一樣，則計數器的值增加。
如果不是，則計數器的值減少。
如果計數器變為0，則將下一個元素選為指定的元素。
加加減減過後，最後剩下的就是真正的主要元素。

PS: 假設我們一開始挑到錯的元素，那也不需要擔心，因為不論如何增減最後都會是主要元素勝出。
可以把它想像成是許多的軍團在戰鬥，戰鬥方式是一個兵換一個兵，假設有一個軍團士兵數量大於所有軍團，最後活下來的一定是這個軍團的士兵。
更不用說其他數量比較小的兵團之間存在著互相攻擊的可能，所以最後勝出的一定是最大的軍團。

public class Solution {
	public int MajorityElement(int[] nums) {
        int count=0;
        int candidate=0;
        foreach(int i in nums){
            if(count==0){
                 candidate = i;
                 count++;
            }else if(candidate == i){
                count++;
            }else{
                count--;
            }            
        }
        return candidate;
    }
}

複雜度分析：

時間複雜度：由於要檢查所有的數字，因此時間複雜度為O(n)。
空間複雜度：使用空間沒有變化，因此空間複雜度為O(1)。

學習重點

投票法 Boyer–Moore Majority Vote Algorithm