169. Majority Element

▶ 整数数组中有一个数出现的频数超过了数组长度的一半，求这个数

● 自己的代码，27 ms，使用散列表，最快的解法算法与之相同，但是用的数据结构是 map

 1 class Solution
 2 {
 3 public:
 4     int majorityElement(vector<int>& nums)
 5     {       
 6         const int n = nums.size();
 7         unordered_map<int, int> table;
 8         int i;
 9         for (i = 0; i < n; i++)
10         {
11             if (table.find(nums[i]) == table.end())
12                 table[nums[i]] = 1;
13             else
14                 table[nums[i]]++;
15         }
16         for (i = 0; i < n; i++)
17         {
18             if (table[nums[i]] > n / 2)
19                 return nums[i];
20         }
21         return -1;
22     }
23 };

● 大佬的解法，16 ms，摩尔投票算法（Boyer-Moore Voting Algorithm），时间复杂度 O(n) 空间复杂度 O(1) 。

■ 从头扫描原数组时对 nums[ 0 ] 计数，新元素等于 nums[ 0 ] 时计数加一，不等于 nums[ 0 ] 时计数减一，如果扫描完第 k 元素时计数减到了 0，说明在第 0 到第 k 元素中 nums[ 0 ] 和其他元素各有 ( k +1 ) / 2 个

■ 这时考虑把第 0 到第 k 元素砍掉：① 若 nums[ 0 ] 本来就是所求的众数，砍掉这段后 nums[ 0 ] 在剩下的部分中仍然具有 “频数超过一半” 的性质；②若 nums[ 0 ] 不是所求的众数，则由于砍掉的其他元素个数之和不超过 nums[ 0 ]（极端情况是其他 ( k +1 ) / 2 个元素都相等，它是所求众数的另一个有力竞争者），所以也不影响剩余数组中真正的所求众数的性质

■ 若数组还有剩余，则取下一个元素作为被计数的元素，重复以上过程。这样就能在最后一段中获得所求众数（完成扫描后计数器应当 ≥ 0）。

■ 注意该算法只能用于计算出现次数超过原数组长度一半的情况（如 [ 1，1，1，2，2，3，3 ] 就不行），当数组没有满足该条件的数字时，将会返回最后一段的被计数元素

 1 class Solution
 2 {
 3 public:
 4     int majorityElement(vector<int>& nums)
 5     {
 6         const int n = nums.size();
 7         int i, count, numMajor; 
 8         for (int i = count = numMajor = 0; i < n; i++)
 9         {
10             if (count == 0)
11                 numMajor = nums[i];
12             if (numMajor == nums[i])
13                 count++;
14             else
15                 count--;
16         }
17         return numMajor;
18     }
19 };

● 其他方法（后接时间复杂度 / 空间复杂度）：逐项计数法 O(n) / O(1)，排序法 O(n log n) / O(1) ，分治法 O(n log n) / O(log n) 。