題目描述

解法一：暴力解

定義一個數組C用于存放nums數組中每個數出現的次數，然后再遍歷C，判斷C【i】是否大于? n/2 ?，如果是，則返回該元素（計數排序）
代碼實現：

class Solution {
public:int majorityElement(vector<int>& nums) {int n = nums.size();//需要使用哈希表unordered_map<int,int> counts;for(int i=0;i<n;i++){counts[nums[i]]++;}//遍歷哈希表for(auto const&pair:counts){if(pair.second>n/2){return pair.first;}}return -1;}
};

執行結果：

復雜度分析：
時間 O(n)
空間 O(n)

解法二 排序法

先排序nums，如果存在一個數出現的次數超過了數組長度的一半，那么將數組排序后，這個數必然會出現在數組中間的位置。
代碼實現

class Solution {
public:int majorityElement(vector<int>& nums) {int n = nums.size();sort(nums.begin(),nums.end());return nums[n/2];}
};

執行結果

復雜度分析
時間:排序的時間復雜度為O(nlogn)
空間:O(1)

解法三：Boyer-Moore 投票算法 (最優解)

思路： 這是一個非常巧妙的算法。可以想象成不同陣營的人進行“消耗戰”。

1. 我們維護一個 candidate (候選人) 和一個 count (計數器)。
2. 遍歷數組，如果 count 為 0，就將當前元素設為 candidate。
3. 如果當前元素和 candidate 相同，count 加 1。
4. 如果當前元素和 candidate 不同，count 減 1 (相當于一組“同歸于盡”)。
5. 由于眾數的數量超過了其他所有數字數量的總和，它最后一定會留下來成為 candidate。

實現代碼

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

執行結果

復雜度分析
時間O(n)
空間O(1)