Majority Element

題目說明

給定一組長度為n的數列，回傳出現次數大於⌊n/2⌋(不超過n/2的整數中最大的一個)的數。

範例

Example 1:
Input: nums = [3,2,3]
Output: 3

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

限制條件和特別需求

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9
• Follow-up: Could you solve the problem in linear time and in O(1) space

思路

最直覺的方法是，直接用個額外的空間存所有數出現的次數，再回傳大於特定次數的值即可。(詳見文末另解)，但這樣時間複雜度為O(n)，空間複雜度亦為O(n)。

題目希望能用 O(1) 的空間複雜度來解決，勢必要再想想其他作法。
首先，拆解題目意思後可推測出: 有一個特定的值，出現次數過半，為眾數，好，那怎麼找到眾數呢?
舉個例子來說，要舉辦一個票選活動，得到票數最多(眾數)的那個就是最有影響力的，假設票為[A B A A A B C]，開票時若A B 各一票可以當作同分抵銷(不考慮得票數，只是要選最多的話)，因為沒有任何人佔優勢!，後面出現了三個A則需紀錄多3次，又出現了B代表可以消掉一個A帶來的影響，紀錄更新成A多2次，又出現了個C，一樣消掉一個A帶來的優勢，最後得到的A就是眾數了。(被我講得很複雜......不知道有沒有表達清楚)

做法大致為
宣告 targe(眾數)，count(占優勢數量)

1. 先將第一個數給target，並記錄count=1
2. 依序比對後面的數:
   若新數與target相同，將count+1
   若新數與target不同且count=0，將target換成新數 (因為前面都是打平的狀態，所以出現的新數就是當前佔優勢的數)
   若新數與target不同且count不為0，將count-1 (消掉那個優勢)
   依序上述規則往後比對，直到結束。

C++ 程式碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 1;
        int target = nums[0];
        for (int i=1; i<nums.size(); i++) {
            if (nums[i] != target && count == 0) {
                target = nums[i];
                count++;
            }
            else if (nums[i] != target)
                count--;
            else
                count++;
        }
        return target;
    }
};

Python3 程式碼

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 1
        target = nums[0];
        for i in range(1,len(nums)):
            if nums[i] != target and count == 0:
                target = nums[i]
                count += 1
            elif nums[i] != target and count != 0:
                count -= 1
            else:
                count += 1
        return target

另解 C++ 程式碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int times = nums.size()/2;
        map<int, int> table;
        for (int i=0;i<nums.size();i++) {
            table[nums[i]]++;
        }
        
        map<int, int>::iterator it;
        for (it = table.begin(); it != table.end(); it++) {
            if (it->second > times)
                return it->first;
        }
        return 0;    
    }
};