LeetCode如何求數組中的絕對眾數

這篇文章主要為大家展示了“LeetCode如何求數組中的絕對眾數”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“LeetCode如何求數組中的絕對眾數”這篇文章吧。

定義：絕對眾數就是一個數在一組數中個數超過1/2的數。

比如給你一個長度為N的整形數組：

[13,12,53,12,23,343,12,12]

要求出他們之中出現次數超過N/2的元素（假定一個數組中必定會有這樣的元素），你會怎么求？若你是暴力求解，時間復雜度為O(n^2)，那就low啦！

六種算法，括號中是我測試出來的每個算法通過OJ的平均時間，我們來一個一個地講解。

1. 哈希表 (22ms)

2. 排序法 (23ms)

3. 隨機數法 (19ms)

4. 摩爾投票法 (19ms)

5. 分治法 (26ms)

6. 位操作法 (25ms)

一、哈希表法

代碼： 

    int majorityElement(std::vector<int> &nums){

        std::map<int, int>counter;

        for (int i = 0; i < nums.size(); ++i)

            if(++counter[nums[i]] > nums.size()/2)

                return nums[i];

    }

利用哈希表，將每個數值的次數存放起來，遇到一個就對應加一，直到這個數值的次數大于n/2為止(注意只可能有一個數，出現的次數大于n/2).

二、排序法

代碼：

int majorityElement(std::vector<int> &nums){

    nth_element(nums.begin(),nums.begin()+nums.size()/2,nums.end());

    return nums[nums.size()/2];

}

代碼最簡潔，僅僅兩句。也很容易理解，運用了STL中的nth_element(). 通過調用nth_element(start, start+n, end)方法，可以使第n個大的數值的位置之前的元素都小于這個位置的元素，這個位置之后的元素都大于這個位置的元素。但是他們不一定是有序的。由于我們的絕對眾數出現的次數大于n/2，所以排序后第n/2大的元素一定是這個絕對眾數。

三、隨機數法

代碼：

    int majorityElement(std::vector<int> &nums){

        srand((unsigned)time(NULL));

      //得到隨機數種子

        while (1) {

            int counters = 0;

            int index = rand() % nums.size();

            for (int i = 0; i < nums.size(); ++i) {

                if (nums[index] == nums[i]){

                    ++counters;

                }

                if (counters > nums.size()/2){

                    return nums[index];

                }

            }

        }

    }

原理：隨機找到一個數然后計算這個數組里這個數出現的次數，若大于n/2則返回這個數。

我一開始以為這個算法會非常慢，因為它最壞情況是O(n^2)，但出乎意料，44個測試的平均結果中，它幾乎是最快的算法（19ms），和摩爾投票法相當。

四、摩爾投票法（動態規劃）

代碼：

    int majorityElement(std::vector<int> &nums){

        int major = 0, counters = 0;

        for (int i = 0; i < nums.size(); ++i) {

            if(!counters){

                major = nums[i];

                counters = 1;

            }

            else

                counters += (major == nums[i]) ? 1:-1;

        }

        return major;//因為假設一定存在絕對眾數，所以可以直接返回

    }

原理：定位major為數組中的某個數，遇到同樣的數加一，不同的數減一，若為0則去掉這個定位，重新定位另外一個數，最后要么返回絕對眾數，要么不存在絕對眾數，由于題目中已經假設一定存在絕對眾數，所以不存在的情況不需要考慮。

五、分治法

代碼：

    int majorityElement(std::vector<int> &nums){

        return majority(nums, 0, nums.size()-1);

    }

    int majority(std::vector<int> &nums,int left,int right){

        if (left == right) {

            return nums[left];

        }

        int mid = left + ((right - left) >> 1);

        int lm = majority(nums, left, mid);

        int rm = majority(nums, mid + 1, right);

        if(lm == rm){

            return rm;

        }

        return std::count(nums.begin() + left, nums.begin() + right + 1, lm) > std::count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm;

    }

原理：通過分治的思想計算出左右兩邊出現次數最多的數，然后進行比較，看哪個出現的次數更多，返回次數更多的那一個。值得注意的是這里用到了STL里的count方法，它使用一對迭代器和一個值做參數，將值出現的次數返回。

PS:中間計算mid的時候用到了位操作符，>>1其實就是除以2. 不能直接(left+right)/2,因為left+right可能會溢出。

六、位操作法

代碼：

    int majorityElement(vector<int>& nums) {

        int major = 0;

        for (int i = 0,mask = 1; i < 32; ++i,mask <<= 1) {

            int bitCounts = 0;

            for (int j = 0; j < nums.size(); ++j) {

                if(nums[j] & mask) bitCounts++;

                if (bitCounts > nums.size()/2) {

                    major |= mask;

                    break;

                }

            }

        }

        return major;

    }

原理：這是最有趣的一個算法，它算的是每個數的bit(位)，若所有數字的某個bit(位)的個數加起來大于一半，則絕對眾數一定有這個位，把這個位的值加起來，最后得到的結果就是絕對眾數。

PS:(major |= mask 中的 |= 是按位或，其實就相當于+=),(& 就是“與”運算符，返回兩個數值中位置一樣的位的值)

若還是無法理解，希望下面這張圖能夠幫助你理解這個算法。字丑見諒~

以上是“LeetCode如何求數組中的絕對眾數”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！