尋找多數(shù)元素這一問題主要運用了：Majority Vote Alogrithm（最大投票算法）
1.Majority Element

? ? ?1)description

? ? ? ? Given an array of size?n, find the majority element. The majority element is the element that appears?more than?? n/2 ??times.

? ? ? ? You may assume that the array is non-empty and the majority element always exist in the array.

? ? ? ? 注意3點：這里的多數(shù)元素必須嚴格大于? n/2 ?（向下取整）、題目假定數(shù)組非空、假定最大元素一定存在(并且我們可以知道滿足要求的元素僅1個)。

? ? ? ? eg:[1,2,7,2,2,5,10,2,2] ? n=9 ?最多數(shù)元素為2，因為它出現(xiàn)次數(shù)為5>? 9/2 ?=4.

?? ? 2)solutions

? ? ? ?鏈接中有l(wèi)eetcoder的六種方案，例如最直觀的哈希表：map遍歷時通過對相同數(shù)組元素逐一累加可以篩選出滿足條件的元素，這一方案對Majority Element II也適用；或者通過對數(shù)組先排序，那么取出數(shù)組索引為? n/2 ?的元素即可；又有隨機抽取數(shù)組中的元素然后求其出現(xiàn)次數(shù)，由于最多數(shù)元素為? n/2 ?個，所以最糟情況下猜了? n/2 ?次；分治法；最大投票算法。?? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ?3)最大投票算法原理：

? ? ? ? 遍歷數(shù)組,當(dāng)碰到兩個不一樣的數(shù)字時,將這兩個數(shù)字同時丟棄，這兩個數(shù)字中可能有一個為 Majority Element,也可能兩個都不為Majority Element.因為k?大于?n/2,所以在最差情況下(每次移除不同數(shù)字時都包含一個Majority Element),我們?nèi)匀荒軌虮ＷC最后得到的數(shù)字是Majority Element.總之：在原序列中去除兩個不同的元素后，在原序列中的多數(shù)元素在新序列中還是多數(shù)元素。 ? ? ? ? ? ? ? ? ? ??

? ? ? ?根據(jù)《算法設(shè)計技巧與分析》書中的算法可以寫出如下非遞歸代碼（書中為遞歸版本并且附有檢查候選的最多數(shù)元素是否存在）：

class Solution { public:int majorityElement(vector<int>& nums) {int j,candidate,count; //candidate代表候選解即最多數(shù)元素，count代表票數(shù)for (j = 0; j < nums.size(); j++){candidate = nums[j]; count = 1; //起初假定第一個元素即為candidate且票數(shù)為1，當(dāng)票數(shù)count=0時就換candidatewhile (j < nums.size() - 1 && count>0){j = j + 1;if (nums[j] == candidate) count++; //當(dāng)下一個元素與candidate相等時票數(shù)+1else count--; //否則票數(shù)-1}}return c;} };

?下面代碼和上面完全一樣，只是更直觀一點：

class Solution { public:int majorityElement(vector<int>& nums) {int candidate, count = 0, n = nums.size();for (int i = 0; i < n; i++) {if (count==0) { //票數(shù)為0則換candidate，換了candidate票數(shù)就得變?yōu)?candidate = nums[i];count = 1;}else if(nums[i] == candidate) //下一個元素和candidate相等時票數(shù)+1count++;elsecount--; //不相等票數(shù)-1}return candidate;} };

? ? ? 總結(jié)：因為數(shù)組個數(shù)為n，且最多數(shù)元素個數(shù)>? n/2 ?，所以有且只有1個元素滿足條件，所以設(shè)置了一個candidate和一個計票器count。而?Majority Element II要求是最多數(shù)元素個數(shù)>? n/3 ?,所以至多有2個元素滿足要求，所以需要設(shè)置兩個candidate和兩個計票器count。

2.Majority Element II

? ? ?1)description：Given an integer array of size?n, find all elements that appear more than?? n/3 ??times. The algorithm should run in linear time and in O(1) space.

? ? ?2)思路：我們需要找到三個不同的數(shù)字，然后拋棄掉這三個數(shù)字：首先要判斷是否等于candidate，如果等于candidate那么對應(yīng)的?candidate?必須加一等待其他的數(shù)字來消除它，當(dāng)有一個?candidate?的?count?為 0 時，說明該?candidate?已經(jīng)全部被消除，我們需要設(shè)定新的?candidate?數(shù)字。當(dāng)一個數(shù)字不等于兩個?candidate，同時兩個?candidate?的?count?都不為零。這意味著當(dāng)前這個數(shù)字就是這兩個candidate?等待的第三個數(shù)字。于是這三個數(shù)字被移除，同時它們的的?count?都要減一。? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ??

? ? ? eg：[2,1,1,4,6,1,10] ? ? ? n=7 ? 元素1的個數(shù)為3>? 7/3 ?=2

? ? ? ? ? ? ?[2,1,1,1,10,2,2,1] ? ?n=8 ? 元素1個數(shù)為4>? 8/3 ?=2,元素2的個數(shù)為3>? 8/3 ?=2

? ? ? python代碼：

class Solution(object):def majorityElement(self, nums):""" :type nums: List[int]:rtype: List[int]""" if not nums:return []count1, count2, candidate1, candidate2 = 0, 0, 0, 0 //初始化兩個candidate和兩個countfor n in nums:if n == candidate1: //注意這里的元素值相等和count為0的判斷順序與問題一中正好相反count1 += 1 //這里先判斷元素值與candidate是否相等elif n == candidate2:count2 += 1elif count1 == 0: //再判斷count是否為0candidate1, count1 = n, 1elif count2 == 0:candidate2, count2 = n, 1else:count1, count2 = count1 - 1, count2 - 1return [n for n in (candidate1, candidate2) if nums.count(n) > len(nums) // 3]

?參考：segmentFault

轉(zhuǎn)載于:https://www.cnblogs.com/king-lps/p/6395058.html

總結(jié)

以上是生活随笔為你收集整理的Majority Element(169) Majority Element II(229)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。