<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 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, 因此最后我們需要進行過濾篩選。 這里畫了一個圖,大家可以感受一下: ![](https://img.kancloud.cn/62/07/62078aa7ee3731b8bcdb98c93613723a_1440x1080.jpg) ![](https://img.kancloud.cn/61/8b/618b5f2eb37b0ff218624e524e9f9e82_1440x1080.jpg) ## 關鍵點解析 - 摩爾投票法 - 兩個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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看