題目描述一

這是 LeetCode 上的「169. 多數(shù)元素」，難度為「簡單」。

Tag : 「哈希表」、「摩爾投票」

數(shù)組中占比超過一半的元素稱之為主要元素。給你一個(gè) 整數(shù) 數(shù)組，找出其中的主要元素。

若沒有，返回 -1 。請?jiān)O(shè)計(jì)時(shí)間復(fù)雜度為 n、空間復(fù)雜度為1 的解決方案。

示例 1：

輸入：nums = [3,2,3] 輸出：3

示例 2：

輸入：nums = [2,2,1,1,1,2,2] 輸出：2

方法一：使用哈希表

class Solution {public int majorityElement(int[] nums) {int n = nums.length;Map<Integer, Integer> map = new HashMap<>();for (int x : nums) {map.put(x, map.getOrDefault(x, 0) + 1);if (map.get(x) > n / 2) return x;}return -1;} }

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

方法二：摩爾投票

摩爾投票 ：在集合中尋找可能存在的多數(shù)元素，這一元素在輸入的序列重復(fù)出現(xiàn)并占到了序列元素的一半以上；在第一遍遍歷之后應(yīng)該再進(jìn)行一個(gè)遍歷以統(tǒng)計(jì)第一次算法遍歷的結(jié)果出現(xiàn)次數(shù)，確定其是否為眾數(shù)；如果一個(gè)序列中沒有占到多數(shù)的元素，那么第一次的結(jié)果就可能是無效的隨機(jī)元素。

換句話說，每次將兩個(gè)不同的元素進(jìn)行「抵消」，如果最后有元素剩余，則「可能」為元素個(gè)數(shù)大于總數(shù)一半的那個(gè)。

具體的，我們定義一個(gè)變量 x 來保存那個(gè)可能為主要元素的值，cnt用來記錄該值的出現(xiàn)次數(shù)。然后在遍歷數(shù)組 nums過程中執(zhí)行如下邏輯：

如果 cnt為0：說明之前出現(xiàn)過的x已經(jīng)被抵消完了，更新一下x為當(dāng)前值，出現(xiàn)次數(shù)為1：x = nums[i], cnt = 1；
如果cnt不為0：說明之前統(tǒng)計(jì)的x還沒被抵消完，這是根據(jù) nums[i]與x是否相等進(jìn)行計(jì)算即可：cnt += nums[i] == x ? 1 : -1。
當(dāng)處理完nums之后，我們得到了一個(gè)「可能」的主要元素。注意只是可能，因?yàn)槲覀冊谔幚磉^程中只使用了x和cnt來記錄，我們是無法確定最后剩下的x是經(jīng)過多次抵消后剩余的主要元素，還是只是不存在主要元素的數(shù)組中的無效隨機(jī)元素。

因此我們需要再進(jìn)行一次遍歷，檢查這個(gè)「可能」的主要元素x的出現(xiàn)次數(shù)是否超過總數(shù)一半。

代碼：

class Solution {public int majorityElement(int[] nums) {int n = nums.length;int x = -1, cnt = 0;for (int i : nums) {if (cnt == 0) {x = i;cnt = 1;} else {cnt += x == i ? 1 : -1;}}cnt = 0;for (int i : nums) if (x == i) cnt++;return cnt > n / 2 ? x : -1;} }

題目描述二

這是 LeetCode 上的「229. 多數(shù)元素二」，難度為「中等」。

Tag : 「哈希表」、「摩爾投票」

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

請?jiān)O(shè)計(jì)時(shí)間復(fù)雜度為 n、空間復(fù)雜度為1 的解決方案。
示例 1：

輸入：nums = [3,2,3] 輸出：[3]

示例 2：

輸入：nums = [1] 輸出：[1]

直接用摩爾投票

class Solution {public List<Integer> majorityElement(int[] nums) {// 根據(jù)反證法可以證明最多有兩個(gè)數(shù)大于n/3int n = nums.length;int a = -1, b = -1; // a,b為當(dāng)前可能計(jì)數(shù)>n/3的數(shù)int c1 = 0, c2 = 0; // c1記錄a的數(shù)量，c2記錄b的數(shù)量for(int i : nums) {if(c1 != 0 && a == i) // a之前出現(xiàn)過c1++;else if(c2 != 0 && b == i) c2++;else if(c1 == 0) { // a位置沒有數(shù)c1++;a = i;} else if(c2 == 0) { // b位置沒有數(shù)c2++;b = i;} else {c1--;c2--;}}c1 = 0;c2 = 0;for(int i : nums) {if(i == a)c1++;else if(i == b)c2++;}List<Integer> ans = new ArrayList<>();if(c1 > n/3)ans.add(a);if(c2 > n/3)ans.add(b);return ans;} }

總結(jié)

以上是生活随笔為你收集整理的摩尔投票（包含题目讲解）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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