[LeetCode] 169. Majority Element 求大多數(shù)

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

• n == nums.length
• 1 <= n <= 5 * 104
• -231 <= nums[i] <= 231 - 1

Follow-up: Could you solve the problem in linear time and in O(1) space?

這是到求大多數(shù)的問題，有很多種解法，其中我感覺比較好的有兩種，一種是用哈希表，這種方法需要 O(n) 的時(shí)間和空間，另一種是用一種叫摩爾投票法 Moore Voting，需要 O(n) 的時(shí)間和 O(1) 的空間，比前一種方法更好。這種投票法先將第一個(gè)數(shù)字假設(shè)為過半數(shù)，然后把計(jì)數(shù)器設(shè)為1，比較下一個(gè)數(shù)和此數(shù)是否相等，若相等則計(jì)數(shù)器加一，反之減一。然后看此時(shí)計(jì)數(shù)器的值，若為零，則將下一個(gè)值設(shè)為候選過半數(shù)。以此類推直到遍歷完整個(gè)數(shù)組，當(dāng)前候選過半數(shù)即為該數(shù)組的過半數(shù)。不仔細(xì)弄懂摩爾投票法的精髓的話，過一陣子還是會忘記的，首先要明確的是這個(gè)叼炸天的方法是有前提的，就是數(shù)組中一定要有過半數(shù)的存在才能使用，下面來看本算法的思路，這是一種先假設(shè)候選者，然后再進(jìn)行驗(yàn)證的算法?，F(xiàn)將數(shù)組中的第一個(gè)數(shù)假設(shè)為過半數(shù)，然后進(jìn)行統(tǒng)計(jì)其出現(xiàn)的次數(shù)，如果遇到同樣的數(shù)，則計(jì)數(shù)器自增1，否則計(jì)數(shù)器自減1，如果計(jì)數(shù)器減到了0，則更換下一個(gè)數(shù)字為候選者。這是一個(gè)很巧妙的設(shè)定，也是本算法的精髓所在，為啥遇到不同的要計(jì)數(shù)器減1呢，為啥減到0了又要更換候選者呢？首先是有那個(gè)強(qiáng)大的前提存在，一定會有一個(gè)出現(xiàn)超過半數(shù)的數(shù)字存在，那么如果計(jì)數(shù)器減到0了話，說明目前不是候選者數(shù)字的個(gè)數(shù)已經(jīng)跟候選者的出現(xiàn)個(gè)數(shù)相同了，那么這個(gè)候選者已經(jīng)很 weak，不一定能出現(xiàn)超過半數(shù)，此時(shí)選擇更換當(dāng)前的候選者。那有可能你會有疑問，那萬一后面又大量的出現(xiàn)了之前的候選者怎么辦，不需要擔(dān)心，如果之前的候選者在后面大量出現(xiàn)的話，其又會重新變?yōu)楹蜻x者，直到最終驗(yàn)證成為正確的過半數(shù)，佩服算法的提出者啊，代碼如下：

C++ 解法一：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int res = 0, cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {res = num; ++cnt;}
            else (num == res) ? ++cnt : --cnt;
        }
        return res;
    }
};

Java 解法一：

public class Solution {
    public int majorityElement(int[] nums) {
        int res = 0, cnt = 0;
        for (int num : nums) {
            if (cnt == 0) {res = num; ++cnt;}
            else if (num == res) ++cnt;
            else --cnt;
        }
        return res;
    }
}

下面這種解法利用到了位操作 Bit Manipulation 來解，將這個(gè)大多數(shù)按位來建立，從0到31位，每次統(tǒng)計(jì)下數(shù)組中該位上0和1的個(gè)數(shù)，如果1多，那么將結(jié)果 res 中該位變?yōu)?，最后累加出來的 res 就是過半數(shù)了，相當(dāng)贊的方法，參見代碼如下：

C++ 解法二：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int res = 0, n = nums.size();
        for (int i = 0; i < 32; ++i) {
            int ones = 0, zeros = 0;
            for (int num : nums) {
                if (ones > n / 2 || zeros > n / 2) break;
                if ((num & (1 << i)) != 0) ++ones;
                else ++zeros;
            }
            if (ones > zeros) res |= (1 << i);
        }
        return res;
    }
};

Java 解法二：

public class Solution {
    public int majorityElement(int[] nums) {
        int res = 0, n = nums.length;
        for (int i = 0; i < 32; ++i) {
            int ones = 0, zeros = 0;
            for (int num : nums) {
                if (ones > n / 2 || zeros > n / 2) break;
                if ((num & (1 << i)) != 0) ++ones;
                else ++zeros;
            }
            if (ones > zeros) res |= (1 << i);
        }
        return res;
    }
}

Github 同步地址：

https://github.com/grandyang/leetcode/issues/169

類似題目：

Majority Element II

參考資料：

https://leetcode.com/problems/majority-element/

https://leetcode.com/problems/majority-element/discuss/51613/O(n)-time-O(1)-space-fastest-solution

https://leetcode.com/problems/majority-element/discuss/51612/6-Suggested-Solutions-in-C++-with-Explanations

https://leetcode.com/problems/majority-element/discuss/51611/Java-solutions-(sorting-hashmap-moore-voting-bit-manipulation).

https://leetcode.com/problems/majority-element/discuss/51828/C++-solution-using-Moore's-voting-algorithm-O(n)-runtime-comlexity-an-no-extra-array-or-hash-table

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(169.求大多數(shù))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)求大多數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論