C語言算法金手指摩爾投票法手撕絕大多數(shù)問題
正片開始
概念
嘛是摩爾投票法?
簡單來說就是投票法,算法解決的問題是如何在任意多的候選人,選出獲得票數(shù)最多的那個。常見的算法是掃描一遍選票,也就是遍歷,對每個候選人進行統(tǒng)計的選票進行統(tǒng)計。
那我遍歷難道不香嗎?
這里就要講一下投票法的過人之處
優(yōu)點
當(dāng)執(zhí)行有序情況時,只要找到中位數(shù),然后檢查中位數(shù)的個數(shù)是否超過選票的一半即可。但是當(dāng)對象的數(shù)目不定時,統(tǒng)計選票可能會執(zhí)行較長時間,相比原來的時間復(fù)雜度 O(n) ,可能需運行 O(n^2) 的時間。
針對無序且對象不定的情況,摩爾投票法應(yīng)運而生。
算法核心
摩爾投票法的關(guān)鍵就是抵消和計數(shù),抵消過程類似于是在進行投票,然后計數(shù)我們可以腦補一個情形:當(dāng)三人中的一人得票數(shù)遠超其他兩人時,我們就可以進行等量對消,消完還有票的自然就是得票數(shù)最多的那個,模擬如下:(ppt手殘勿噴)
實現(xiàn)
基本思路就是由一個計數(shù)器維護,在進行比較過程中,不同票消掉,相同票保留,如果消的沒有了就直接放進去然后繼續(xù)上述過程,直到維護對象只剩一個,就是我們要找的最大得票者(眾數(shù))。
基于LeetCode真題實踐,先看一個初級栗子:
169. 多數(shù)元素
給定一個大小為 n 的數(shù)組,找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ⌊ n/2 ⌋ 的元素。你可以假設(shè)數(shù)組是非空的,并且給定的數(shù)組總是存在多數(shù)元素。
示例:
輸入:[2,2,1,1,1,2,2]
輸出:2
來源:力扣(LeetCode)
我最初的思路是哈希思想,qsort 之后用最大的元素 malloc 一塊新的空間,桶排后用 count 進行++,最后輸出 count 最大的。有點麻煩而且我忽視了一個最大的問題就是負數(shù)的存在,垮掉~
根據(jù)我們算法的思路,針對目標(biāo)數(shù)組 nums,首先創(chuàng)建一個變量來執(zhí)行計數(shù)器 count 再創(chuàng)建一個新數(shù)組 a 進行比對,因為始終是目標(biāo)數(shù)組的內(nèi)部元素比較,我可以直接把 nums 首元素賦給 a ,比較時從第二個元素開始和 a 比較,如果相同,count ++;不同消掉,count --;沒有了就往里拿。
int majorityElement(int* nums, int numsSize){ int count = 1; int a = nums[0]; for(int i =1;i<numsSize;i++) { if(nums[i]==a) { count++; } else { count--; } if(count==0) { a = nums[i+1]; } } return a; }
格局抬高
現(xiàn)在整一道硬菜,直接上升級版:
229. 求眾數(shù) II
給定一個大小為 n 的整數(shù)數(shù)組,找出其中所有出現(xiàn)超過 ⌊ n/3 ⌋ 次的元素。
示例 :
輸入:[1,1,1,3,3,2,2,2]
輸出:[1,2]
還是那句話,題目越少眼淚越飽,短小精悍的題 nnd 硬磨了我一個下午,桶是肯定桶不了的,哈希又沒學(xué),不做吧心里太不舒服,這里就又有我摩爾投票法的一席之地了
注意,題目給的是超過 n/3 次的元素,這很重要,其實就是在暗示我們結(jié)果至多只會有三種情況:沒有眾數(shù)或者一個眾數(shù)或者兩個眾數(shù);但是頭疼的是咱之前的摩爾投票法好像行不通,因為這里對象不定,如果出現(xiàn)了兩個眾數(shù)我的 “ 票 ” 該怎么投?
將之前的格局打開,我們可以將所有數(shù)字分為兩類,> n/3 的元素 和 <= n/3 的元素,其中大于 n/3 的元素最多只有兩個。因此可以設(shè)置三個變量,進行相對抵消,這里我們不妨再引入一個容器 b,再用一個新的計數(shù)器 count2 來進行維護,當(dāng)三個元素相同時,count++,不同就抵消,為 0 就用把這個數(shù)放進去,基本思想和上面是差不多的:
int a = nums[0]; int b = nums[1]; int count1, count2 = 0; for (int i = 0; i < numsSize; i++) { if (a == nums[i]) { count1++; continue; } else if (b == nums[i]) { count2++; continue; } else { count1--; count2--; } if (count1 < 0) { a = nums[i]; count2++; count1 = 1; } if (count2 < 0) { b = nums[i]; count1++; count2 = 1; } }
還沒完,因為數(shù)組可能存在一個眾數(shù)或者沒有眾數(shù)的情況,我們還需要再次遍歷來統(tǒng)計我們篩選的眾數(shù)的出現(xiàn)次數(shù)是否符合題目要求的大于n/3 以及排除數(shù)組為空或單項的情況:
count1 = 0; count2 = 0; for (int i = 0; i < numsSize; i++) { if (a == nums[i]) { count1++; } else if (b == nums[i]) { count2++; } } if (numsSize <= 1) { *returnSize = numsSize; return nums; }
最后直接依次放入一塊新的空間再返回即可,全部代碼如下:
int* majorityElement(int* nums, int numsSize, int* returnSize) { if (numsSize <= 1) { *returnSize = numsSize; return nums; } int a = nums[0]; int b = nums[1]; int count1, count2 = 0; for (int i = 0; i < numsSize; i++) { if (a == nums[i]) { count1++; continue; } else if (b == nums[i]) { count2++; continue; } else { count1--; count2--; } if (count1 < 0) { a = nums[i]; count2++; count1 = 1; } if (count2 < 0) { b = nums[i]; count1++; count2 = 1; } } count1 = 0; count2 = 0; for (int i = 0; i < numsSize; i++) { if (a == nums[i]) { count1++; } else if (b == nums[i]) { count2++; } } int* c = (int*)malloc(sizeof(int) * 2); *returnSize = 0; if (count1 > numsSize / 3) { c[(*returnSize)++] = a; } if (count2 > numsSize / 3) { c[(*returnSize)++] = b; } return c; }
家人們明白了嗎,那今天就到這里,摸了。
以上就是C語言算法金手指摩爾投票法手撕絕大多數(shù)問題的詳細內(nèi)容,更多關(guān)于C語言摩爾投票算法的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C語言scandir函數(shù)獲取文件夾內(nèi)容的實現(xiàn)
scandir?函數(shù)用于列舉指定目錄下的文件列表,本文主要介紹了C語言scandir函數(shù)獲取文件夾內(nèi)容的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2024-03-03使用c++調(diào)用windows打印api進行打印的示例代碼
這篇文章主要介紹了使用c++調(diào)用windows打印api進行打印的示例代碼,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06C語言常用庫函數(shù)的使用及模擬實現(xiàn)詳解例舉
C語言庫函數(shù)是把自定義函數(shù)放到庫里,是別人把一些常用到的函數(shù)編完放到一個文件里,供程序員使用,下面讓我們一起來詳細了解它2022-04-04