第一次提交的思路和代碼是的你沒有想錯我是直接拿著上一篇解決2013年408的解法直接去提交洛谷P2397 yyy loves Maths VI (mode) / 摩爾投票這道題的。結(jié)果也是不孚眾望沒有打錯字啊就是這個孚很絕望啊只是過了一部分的點因為考慮到了這個數(shù)據(jù)的范圍但是沒有考慮這個數(shù)組空間的大小?；仡櫼幌滤悸返谝槐楸闅v找候選人第二遍遍歷驗證候選人是否真的出現(xiàn)超過 n/2 次數(shù)組作為參數(shù)傳入需要知道長度時間O(N),數(shù)組也為ON感覺沒啥大問題于是我很自然地寫出了下面這段代碼就提交去了#includebits/stdc.h using namespace std; int vote(int num[], int n) { int cand num[0]; int hp 1; // 第一遍找候選人 for(int i 1; i n; i) { if(hp 0) { cand num[i]; hp 1; } else if(cand num[i]) hp; else hp--; } // 第二遍驗證是否確實超過 n/2 if(hp 0) return -1; hp 0; for(int i 0; i n; i) { if(num[i] cand) hp; } return hp n / 2 ? cand : -1; } int main() { int n; cin n; int num[n]; // 變長數(shù)組存全部數(shù)據(jù) for(int i 0; i n; i) cin num[i]; int flag vote(num, n); cout flag; }結(jié)果就是這個很顯然易見爆內(nèi)存了因為除了題目信息意外既然忘記看了這個題目后面的時間限制1.00s 和 內(nèi)存限制 5.00MB了我使用這個數(shù)組產(chǎn)生的空間大小為 2,000,000 × 4B 8,000,000 B是8MB。所以我第二次的優(yōu)化方向為讓這個數(shù)組變小一點或者最好不使用數(shù)組這樣花費的空間變小不就可以通過了嗎。第二次提交的思路優(yōu)化和代碼優(yōu)化更深層的反思我犯了一個根本性的錯誤摩爾投票法根本不需要存整個數(shù)組摩爾投票的核心思想是來一個抵消一個遇到相同的數(shù) → 票數(shù) 1遇到不同的數(shù) → 票數(shù) -1同歸于盡票數(shù)為0 → 換候選人這完全是流式處理只需要記住當前候選人和當前票數(shù)兩個變量即可。因為在408中出現(xiàn)了這個數(shù)組在這個題目當中有這個輸入一行整數(shù)所以下意識的想到使用數(shù)組也就是把它寫成了先存再算白白浪費了 O(n) 的空間我們完全可以把這個過程抽象成為打擂臺“排好隊一個一個來來一個處理一個這樣等到遍歷完數(shù)組整個過程也是結(jié)束了。代碼如下#includebits/stdc.h using namespace std; int main() { int n,cand0; cinn; int hp0; for(int i0;in;i) { int x; cinx; if(hp0) { candx; hp; } else if(candx) hp; else hp--; } if(hp0) cand-1; coutcand; }另外要說明的是為什么這里不需要第二遍驗證重新讀一遍題目一共有 n 個正整數(shù)ai 他讓 redbag 找眾數(shù)。他還特意表示這個眾數(shù)出現(xiàn)次數(shù)超過了一半。 他的意思是N個正整數(shù)里面必然存在如果不存在這個主元素在這個題目當中一定會說明這個主元素不存在要怎么辦比如輸出-1表示這種很顯然就是不存在這個特殊的情況。這種流式處理思維是這次提交得到的最大的收獲代碼還能這樣去優(yōu)化空間以前考慮的都是在時間層面上的這個思路望我以后一定要記得住。