【leetcode刷題】11.多數元素—

從第一個數開始count=1，遇到相同的就加1，遇到不同的就減1，減到0就重新換個數開始計數，總能找到最多的那個

——leetcode此題熱評

前言

哈嘍，大家好，我是一條

糊涂演算法，難得糊涂

昨天面試位元組，切實感受到了刷演算法帶來的提升

生命不息，刷題不止

Question

169. 多數元素

難度：簡單

給定一個大小為 n 的陣列，找到其中的多數元素，多數元素是指在陣列中出現次數大于 ? n/2 ? 的元素，

你可以假設陣列是非空的，并且給定的陣列總是存在多數元素，

示例 1：
輸入：[3,2,3]
輸出：3
示例 2：
輸入：[2,2,1,1,1,2,2]
輸出：2
進階：

嘗試設計時間復雜度為 O(n)、空間復雜度為 O(1) 的演算法解決此問題，

Solution

一條開始采用的hashmap計數法，不用想，結果肯定超時了

足足17ms

HashMap<Integer, Integer> map = new HashMap<>();
       for (int i = 0; i < nums.length; i++) {
           if (map.containsKey(nums[i])){
               map.put(nums[i],map.get(nums[i])+1);
               if (map.get(nums[i])>nums.length/2){
                   return nums[i];
               }
           }else {
               map.put(nums[i],1);
           }

       }
       return nums[0];

后來發現有個方法叫摩爾投票

摩爾投票法

核心就是對拼消耗，

玩一個諸侯爭霸的游戲，假設你方人口超過總人口一半以上，并且能保證每個人口出去干仗都能一對一同歸于盡，最后還有人活下來的國家就是勝利，

那就大混戰唄，最差所有人都聯合起來對付你（對應你每次選擇作為計數器的數都是眾數），或者其他國家也會相互攻擊（會選擇其他數作為計數器的數），但是只要你們不要內斗，最后肯定你贏，

最后能剩下的必定是自己人，

定義一個計數器count=1，多數元素cur=numsp[0]
如果當前數字和多數元素相同，count++
如果當前數字和多數元素不同,count--
如果count==0，更換cur的值

理解了摩爾投票法后，良心推薦一道進階的題目：求眾數Ⅱ

Code

所有leetcode代碼已同步至github

歡迎star

class Solution {
    public int majorityElement(int[] nums) {
        int cand_num = nums[0], count = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (cand_num == nums[i]) {
                ++count;
            }else if (--count == 0) {
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
}

Result

復雜度分析

時間復雜度：O(N)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290177.html

標籤：其他

上一篇：關于 Unity 啟動彈 Your project was last saved with a different version of Unity 彈窗的解決辦法

下一篇：【微軟演算法面試高頻題】跳躍游戲

【leetcode刷題】11.多數元素——Java版

前言

Question

169. 多數元素

Solution

Code

Result