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