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.length1 <= n <= 5 * 10^4-10^9 <= nums[i] <= 10^9Follow-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(占优势数量)

先将第一个数给target，并记录count=1依序比对后面的数:
若新数与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;        }};