多數(shù)元素

也叫數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字

給定一個(gè)大小為 *n *的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ? n/2 ? 的元素。

你可以假設(shè)數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。

示例 1：

輸入：[3,2,3]
輸出：3

示例 2：

輸入：[2,2,1,1,1,2,2]
輸出：2

方法一：排序+取中間元素

public int majorityElement(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    return nums[n / 2];
}

方法二：HashMap
統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)次數(shù)，最后再做比較

方法三：摩爾投票

public int majorityElement(int[] nums) {
    int candidate = 0;
    int count = 0;
    for (int num : nums) {
        count += candidate == num ? 1 : -1;
        if (count < 0) {
            candidate = num;
            count = 1;
        }
    }
    return candidate;
}

摩爾投票法，解決的問(wèn)題是如何在任意多的候選人中，選出票數(shù)超過(guò)一半的那個(gè)人。注意，是超出一半票數(shù)的那個(gè)人。

假設(shè)投票是這樣的，[A, C, A, A, B]，ABC 是指三個(gè)候選人。

第一張票與第二張票進(jìn)行對(duì)坑，如果票不同則互相抵消掉；
接著第三票與第四票進(jìn)行對(duì)坑，如果票相同，則增加這個(gè)候選人的可抵消票數(shù)；
這個(gè)候選人拿著可抵消票數(shù)與第五張票對(duì)坑，如果票不同，則互相抵消掉，即候選人的可抵消票數(shù) -1。
但這不意味著這個(gè)候選人的票數(shù)一定能超過(guò)一半，例如 [A, B, C] 的抵消階段，最后得到的結(jié)果是 [C,1]，C 候選人的票數(shù)也未能超過(guò)一半的票數(shù)。

在這里發(fā)現(xiàn)了一個(gè)優(yōu)化，如果最后得到的可抵消票數(shù)是 0 的話，那他已經(jīng)無(wú)緣票數(shù)能超過(guò)一半的那個(gè)人了。因?yàn)楸緛?lái)可能有希望的，但是被后面的一張不同的票抵消掉了。所以，在這里可以直接返回結(jié)果，無(wú)需后面的計(jì)算了。
如果最后得到的抵消票數(shù)不為 0 的話，那說(shuō)明他可能希望的，這是我們需要一個(gè)階段來(lái)驗(yàn)證這個(gè)候選人的票數(shù)是否超過(guò)一半—— 計(jì)數(shù)階段。

所以摩爾投票法分為兩個(gè)階段：抵消階段和計(jì)數(shù)階段。
抵消階段：兩個(gè)不同投票進(jìn)行對(duì)坑，并且同時(shí)抵消掉各一張票，如果兩個(gè)投票相同，則累加可抵消的次數(shù)；
計(jì)數(shù)階段：在抵消階段最后得到的抵消計(jì)數(shù)只要不為 0，那這個(gè)候選人是有可能超過(guò)一半的票數(shù)的，為了驗(yàn)證，則需要遍歷一次，統(tǒng)計(jì)票數(shù)，才可確定。

摩爾投票法經(jīng)歷兩個(gè)階段最多消耗O(2n) 的時(shí)間，也屬于 O(n)的線性時(shí)間復(fù)雜度，另外空間復(fù)雜度也達(dá)到常量級(jí)。

為了和下一題統(tǒng)一寫(xiě)成：

public int majorityElement(int[] nums) {
    int candidate = nums[0];
    int vote = 0;
    for (int num : nums) {
        if (vote > 0 && num == candidate) {
            vote++;
        } else if (vote == 0) {
            candidate = num;
            vote = 1;
        } else {
            vote--;
        }
    }
    return candidate;
}

求眾數(shù) II

給定一個(gè)大小為 *n *的整數(shù)數(shù)組，找出其中所有出現(xiàn)超過(guò) ? n/3 ? 次的元素。

摩爾投票
題目可以看作是：在任意多的候選人中，選出票數(shù)超過(guò)? 1/3 ?的候選人。
我們可以這樣理解，假設(shè)投票是這樣的 [A, B, C, A, A, B, C]，ABC 是指三個(gè)候選人。
第 1 張票，第 2 張票和第3張票進(jìn)行對(duì)坑，如果票都不同，則互相抵消掉；
第 4 張票，第 5 張票和第 6 張票進(jìn)行對(duì)坑，如果有部分相同，則累計(jì)增加他們的可抵消票數(shù)，如 [A, 2] 和 [B, 1]；
接著將 [A, 2] 和 [B, 1] 與第 7 張票進(jìn)行對(duì)坑，如果票都沒(méi)匹配上，則互相抵消掉，變成 [A, 1] 和 `[B, 0] 。

如果至多選一個(gè)代表，那他的票數(shù)至少要超過(guò)一半（? 1/2 ?）的票數(shù)；
如果至多選兩個(gè)代表，那他們的票數(shù)至少要超過(guò) ? 1/3 ? 的票數(shù)；
如果至多選m個(gè)代表，那他們的票數(shù)至少要超過(guò) ? 1/(m+1) ? 的票數(shù)。
所以以后碰到這樣的問(wèn)題，而且要求達(dá)到線性的時(shí)間復(fù)雜度以及常量級(jí)的空間復(fù)雜度，直接套上摩爾投票法。

public List<Integer> majorityElement(int[] nums) {
    // 投票階段
    int candidate1 = nums[0], candidate2 = nums[0];
    int vote1 = 0, vote2 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (vote1 > 0 && nums[i] == candidate1) {
            vote1++;
        } else if (vote2 > 0 && nums[i] == candidate2) {
            vote2++;
        } else if (vote1 == 0) {
            candidate1 = nums[i];
            vote1 = 1;
        } else if (vote2 == 0) {
            candidate2 = nums[i];
            vote2 = 1;
        } else {
            vote1--;
            vote2--;
        }
    }
    // 計(jì)數(shù)階段
    int cnt1 = 0, cnt2 = 0;
    for (int num : nums) {
        if (num == candidate1) {
            cnt1++;
        } else if (num == candidate2) {
            cnt2++;
        }
    }
    // 判斷是否滿足條件
    List<Integer> res = new ArrayList<>();
    if (vote1 > 0 && cnt1 > nums.length / 3) {
        res.add(candidate1);
    }
    if (vote2 > 0 && cnt2 > nums.length / 3) {
        res.add(candidate2);
    }
    return res;
}