這篇文章主要為大家展示了“LeetCode如何求數(shù)組中的絕對(duì)眾數(shù)”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“LeetCode如何求數(shù)組中的絕對(duì)眾數(shù)”這篇文章吧。

網(wǎng)站制作、做網(wǎng)站介紹好的網(wǎng)站是理念、設(shè)計(jì)和技術(shù)的結(jié)合。創(chuàng)新互聯(lián)公司擁有的網(wǎng)站設(shè)計(jì)理念、多方位的設(shè)計(jì)風(fēng)格、經(jīng)驗(yàn)豐富的設(shè)計(jì)團(tuán)隊(duì)。提供PC端+手機(jī)端網(wǎng)站建設(shè)，用營(yíng)銷思維進(jìn)行網(wǎng)站設(shè)計(jì)、采用先進(jìn)技術(shù)開源代碼、注重用戶體驗(yàn)與SEO基礎(chǔ)，將技術(shù)與創(chuàng)意整合到網(wǎng)站之中，以契合客戶的方式做到創(chuàng)意性的視覺化效果。

定義：絕對(duì)眾數(shù)就是一個(gè)數(shù)在一組數(shù)中個(gè)數(shù)超過1/2的數(shù)。

比如給你一個(gè)長(zhǎng)度為N的整形數(shù)組：

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

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

六種算法，括號(hào)中是我測(cè)試出來的每個(gè)算法通過OJ的平均時(shí)間，我們來一個(gè)一個(gè)地講解。

1. 哈希表 (22ms)

2. 排序法 (23ms)

3. 隨機(jī)數(shù)法 (19ms)

4. 摩爾投票法 (19ms)

5. 分治法 (26ms)

6. 位操作法 (25ms)

一、哈希表法

代碼： 

    int majorityElement(std::vector &nums){

        std::mapcounter;

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

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

                return nums[i];

    }

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

二、排序法

代碼：

int majorityElement(std::vector &nums){

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

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

}

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

三、隨機(jī)數(shù)法

代碼：

    int majorityElement(std::vector &nums){

        srand((unsigned)time(NULL));

      //得到隨機(jī)數(shù)種子

        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];

                }

            }

        }

    }

原理：隨機(jī)找到一個(gè)數(shù)然后計(jì)算這個(gè)數(shù)組里這個(gè)數(shù)出現(xiàn)的次數(shù)，若大于n/2則返回這個(gè)數(shù)。

我一開始以為這個(gè)算法會(huì)非常慢，因?yàn)樗顗那闆r是O(n^2)，但出乎意料，44個(gè)測(cè)試的平均結(jié)果中，它幾乎是最快的算法（19ms），和摩爾投票法相當(dāng)。

四、摩爾投票法（動(dòng)態(tài)規(guī)劃）

代碼：

    int majorityElement(std::vector &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;//因?yàn)榧僭O(shè)一定存在絕對(duì)眾數(shù)，所以可以直接返回

    }

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

五、分治法

代碼：

    int majorityElement(std::vector &nums){

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

    }

    int majority(std::vector &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;

    }

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

PS:中間計(jì)算mid的時(shí)候用到了位操作符，>>1其實(shí)就是除以2. 不能直接(left+right)/2,因?yàn)閘eft+right可能會(huì)溢出。

六、位操作法

代碼：

    int majorityElement(vector& 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;

    }

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

PS:(major |= mask 中的 |= 是按位或，其實(shí)就相當(dāng)于+=),(& 就是“與”運(yùn)算符，返回兩個(gè)數(shù)值中位置一樣的位的值)

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

以上是“LeetCode如何求數(shù)組中的絕對(duì)眾數(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！