229. 求眾數(shù) II

給定一個大小為?n?的整數(shù)數(shù)組，找出其中所有出現(xiàn)超過?? n/3 ??次的元素。

懶得跟著另外幾篇題解復(fù)讀一遍，而且leetcode沒綁手機(jī)發(fā)不了帖，還是放B站做一個記錄。

初見題目，首先想到的肯定是Hash map！(破音)? 像這個：

然后擊敗了百分之10的用戶。

直接看題解，得到關(guān)鍵字：摩爾投票。

然后就去維基看了下，發(fā)現(xiàn)了一個令人震驚的事實(shí)：

摩爾投票，摩爾定律，摩爾密碼......這三個摩爾并不是同一個人。

震驚完回來看題解。摩爾投票的原理很簡單：次數(shù)超過n/3次的元素最多只存在兩個，先假設(shè)這兩個元素真的存在。假設(shè)存在兩個，那么把所有數(shù)字分成每三個一組，三個數(shù)字不同就“抵消”，最后一定會剩下那兩個數(shù)字。

比如 1 6?3 5?5 5 6 6 5?6

任意分組，1 6 3 不同，全部抵消。 5 5 5一樣，留下。6 6 5，把?5抵消。剩下不管。

最后剩5和6兩個數(shù)字。

嘛......道理差不多就是這么回事，主要是代碼的實(shí)現(xiàn)我沒看懂。

沒懂的地方是，count++的含義。于是換了思路，我要和自己以外的人戰(zhàn)斗，另外的自己是同伴，遇到了同伴就增加了戰(zhàn)斗的資本，遇到了敵人就戰(zhàn)斗，敵人死掉，我也會死。如果我死了，那么剩下的同伴會繼續(xù)戰(zhàn)斗，如果一個我都沒有了，那么我會被取代。

經(jīng)歷無數(shù)的廝殺后，活下來的就是天選之子，也就是答案。

世界還真是殘酷啊。

其實(shí)是這樣。一開始沒懂count++的意義，因?yàn)樵砟且粔K并沒說要記錄投票數(shù)。但其實(shí)可以這么理解，假設(shè)當(dāng)前數(shù)字是i，count++實(shí)際上記錄的i被分到了多少個組里......因?yàn)殚_始說了，每三個數(shù)字一組，不同的數(shù)字被抵消，相同的留下。當(dāng)count++時，能被用于分組的i增加了，然后i被分到不同數(shù)字的組里就抵消了，當(dāng)count==0，i用完了，再用新的數(shù)去分組(新的數(shù)字仍可能是i)。假設(shè)答案存在，那么它的出現(xiàn)次數(shù)是大于n/3的，然后又是三個數(shù)字一組，所以答案絕對不會被完全抵消，沒被抵消完的就是答案。

世界真是太殘酷了。