leetcode15，Leetcode 169 Majority Element

Given an array of size?n, find the majority element. The majority element is the element that appears?more than?? n/2 ??times.

You may assume that the array is non-empty and the majority element always exist in the array.

題目大意：

給定一個長度為n的數組，尋找其中的“眾數”。眾數是指出現次數大于?? n/2 ? 的元素。

你可以假設數組是非空的并且數組中的眾數永遠存在。（判斷存不存在，可以計算最后一次得到的“眾數”是否是眾數）

leetcode15？?

“投票算法”，設定兩個變量candidate和count。candidate保存當前可能的候選眾數，count保存該候選眾數的出現次數。

遍歷數組num。

如果當前的數字e與候選眾數candidate相同，則將計數count + 1

否則，如果當前的候選眾數candidate為空，或者count為0，則將候選眾數candidate的值置為e，并將計數count置為1。

leetcode 5。否則，將計數count - 1

最終留下的候選眾數candidate即為最終答案。

以上算法時間復雜度為O(n)，空間復雜度為O(1)

?

?

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

LeetCode，?

官方解析：

時間復雜度: O(n2) — 蠻力法: 依次檢查每一個元素是否為眾數

?

時間復雜度: O(n), 空間復雜度: O(n) — 哈希表: 維護一個每一個元素出現次數的哈希表, 然后找到出現次數最多的元素

時間復雜度: O(n log n) — 排序: 在排序后找出連續重復出現次數最多的元素

leetcode 121。平均時間復雜度: O(n), 最壞復雜度: 無窮大?— 隨機算法: 隨機選取一個元素計算其是否為眾數. 如果不是, 就重復上一步驟直到找到為止。?由于選出眾數的概率 > 1 / 2, 因此期望的嘗試次數 < 2

時間復雜度: O(n log n) — 分治法: 將數組拆成2半, 然后找出前一半的眾數A和后一半的眾數B。則全局眾數要么是A要么是B。?如果 A == B, 則它自然而然就是全局眾數。 如果不是, 則A和B都是候選眾數, 則至多只需要檢查這兩個元素的出現次數即可。?時間復雜度, T(n) = T(n/2) + 2n = O(n log n).

時間復雜度: O(n) — Moore投票算法: 我們維護一個當前的候選眾數和一個初始為0的計數器。遍歷數組時，我們看當前的元素x:

• 如果計數器是0, 我們將候選眾數置為 x 并將計數器置為 1
• 如果計數器非0, 我們根據x與當前的候選眾數是否相等對計數器+1或者-1
• 一趟之后, 當前的候選眾數就是所求眾數. 時間復雜度 = O(n).

時間復雜度: O(n) — 位操作法: 我們需要32次迭代, 每一次計算所有n個數的第i位的1的個數。由于眾數一定存在，那么或者1的個數 > 0的個數 或者反過來(但絕不會相同)。 眾數的第i位一定是計數較多數字。

?