# 0229. 求眾數 II ## 題目地址(229. 求眾數 II) <https://leetcode-cn.com/problems/majority-element-ii/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個大小為 n 的數組，找出其中所有出現超過 ? n/3 ? 次的元素。 進階：嘗試設計時間復雜度為 O(n)、空間復雜度為 O(1)的算法解決此問題。 示例 1： 輸入：[3,2,3] 輸出：[3] 示例 2： 輸入：nums = [1] 輸出：[1] 示例 3： 輸入：[1,1,1,3,3,2,2,2] 輸出：[1,2] 提示： 1 <= nums.length <= 5 * 104 -109 <= nums[i] <= 109 ``` ``` ## 前置知識 - 摩爾投票法 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題目和[169.majority-element](169.majority-element.html) 很像。 我們仍然可以采取同樣的方法 - “摩爾投票法”， 具體的思路可以參考上面的題目。 但是這里有一個不同的是這里的眾數不再是超過`1 / 2`,而是超過`1 / 3`。 題目也說明了，超過三分之一的有可能有多個（實際上就是0，1，2三種可能）。 因此我們不能只用一個counter來解決了。 我們的思路是同時使用兩個counter，其他思路和上一道題目一樣。 最后需要注意的是兩個counter不一定都滿足條件，這兩個counter只是出現次數最多的兩個數字。 有可能不滿足出現次數大于1/3， 因此最后我們需要進行過濾篩選。 這里畫了一個圖，大家可以感受一下：   ## 關鍵點解析 - 摩爾投票法 - 兩個counter - 最后得到的只是出現次數最多的兩個數字，有可能不滿足出現次數大于1/3 ## 代碼 JavaScript代碼： ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=229 lang=javascript * * [229] Majority Element II */</span> <span class="hljs-title">/** * @param {number[]} nums * @return {number[]} */</span> <span class="hljs-keyword">var</span> majorityElement = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">const</span> res = []; <span class="hljs-keyword">const</span> len = nums.length; <span class="hljs-keyword">let</span> n1 = <span class="hljs-params">null</span>, n2 = <span class="hljs-params">null</span>, cnt1 = <span class="hljs-params">0</span>, cnt2 = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < len; i++) { <span class="hljs-keyword">if</span> (n1 === nums[i]) { cnt1++; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (n2 === nums[i]) { cnt2++; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (cnt1 === <span class="hljs-params">0</span>) { n1 = nums[i]; cnt1++; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (cnt2 === <span class="hljs-params">0</span>) { n2 = nums[i]; cnt2++; } <span class="hljs-keyword">else</span> { cnt1--; cnt2--; } } cnt1 = <span class="hljs-params">0</span>; cnt2 = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < len; i++) { <span class="hljs-keyword">if</span> (n1 === nums[i]) { cnt1++; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (n2 === nums[i]) { cnt2++; } } <span class="hljs-keyword">if</span> (cnt1 > (len / <span class="hljs-params">3</span>) >>> <span class="hljs-params">0</span>) { res.push(n1); } <span class="hljs-keyword">if</span> (cnt2 > (len / <span class="hljs-params">3</span>) >>> <span class="hljs-params">0</span>) { res.push(n2); } <span class="hljs-keyword">return</span> res; }; ``` ``` Java代碼： ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=229 lang=java * * [229] Majority Element II */</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> List<Integer> <span class="hljs-title">majorityElement</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums)</span> </span>{ List<Integer> res = <span class="hljs-keyword">new</span> ArrayList<Integer>(); <span class="hljs-keyword">if</span> (nums == <span class="hljs-keyword">null</span> || nums.length == <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> res; <span class="hljs-keyword">int</span> n1 = nums[<span class="hljs-params">0</span>], n2 = nums[<span class="hljs-params">0</span>], cnt1 = <span class="hljs-params">0</span>, cnt2 = <span class="hljs-params">0</span>, len = nums.length; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < len; i++) { <span class="hljs-keyword">if</span> (nums[i] == n1) cnt1++; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[i] == n2) cnt2++; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (cnt1 == <span class="hljs-params">0</span>) { n1 = nums[i]; cnt1 = <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (cnt2 == <span class="hljs-params">0</span>) { n2 = nums[i]; cnt2 = <span class="hljs-params">1</span>; } <span class="hljs-keyword">else</span> { cnt1--; cnt2--; } } cnt1 = <span class="hljs-params">0</span>; cnt2 = <span class="hljs-params">0</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < len; i++) { <span class="hljs-keyword">if</span> (nums[i] == n1) cnt1++; <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (nums[i] == n2) cnt2++; } <span class="hljs-keyword">if</span> (cnt1 > len / <span class="hljs-params">3</span>) res.add(n1); <span class="hljs-keyword">if</span> (cnt2 > len / <span class="hljs-params">3</span> && n1 != n2) res.add(n2); <span class="hljs-keyword">return</span> res; } } ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 擴展 如果題目中3變成了k，怎么解決？ 大家可以自己思考一下，我這里給一個參考鏈接：<https://leetcode.com/problems/majority-element-ii/discuss/63500/JAVA-Easy-Version-To-Understand!!!!!!!!!!!!/64925> 這個實現說實話不是很好，大家可以優化一下。 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。