LeetCode如何求數(shù)組中的絕對眾數(shù)

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

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

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

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

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

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

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

哈希表 (22ms)
排序法 (23ms)
隨機數(shù)法 (19ms)
摩爾投票法 (19ms)
分治法 (26ms)
位操作法 (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];
}

利用哈希表，將每個數(shù)值的次數(shù)存放起來，遇到一個就對應(yīng)加一，直到這個數(shù)值的次數(shù)大于n/2為止(注意只可能有一個數(shù)，出現(xiàn)的次數(shù)大于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(). 通過調(diào)用nth_element(start, start+n, end)方法，可以使第n個大的數(shù)值的位置之前的元素都小于這個位置的元素，這個位置之后的元素都大于這個位置的元素。但是他們不一定是有序的。由于我們的絕對眾數(shù)出現(xiàn)的次數(shù)大于n/2，所以排序后第n/2大的元素一定是這個絕對眾數(shù)。

三、隨機數(shù)法

代碼：

    int majorityElement(std::vector<int> &nums){
srand((unsigned)time(NULL));
      //得到隨機數(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];
}
}
}
    }

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

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

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

代碼：

    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;//因為假設(shè)一定存在絕對眾數(shù)，所以可以直接返回
    }

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

五、分治法

代碼：

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

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

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

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

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

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

LeetCode如何求數(shù)組中的絕對眾數(shù)

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

網(wǎng)站題目：LeetCode如何求數(shù)組中的絕對眾數(shù)
文章轉(zhuǎn)載：http://www.jbt999.com/article14/pspjde.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、關(guān)鍵詞優(yōu)化、電子商務(wù)、軟件開發(fā)、App設(shè)計、云服務(wù)器

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：[email protected]。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容