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

前言

哈喽，大家好，我是一條

糊塗算法，難得糊塗

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

生命不息，刷題不止

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)

🌈尋寶

⭐今天是堅持刷題更文的第11/100天

⭐各位的點贊、關注、收藏、評論、訂閱就是一條創作的最大動力

⭐更多算法題歡迎關注專欄《leetcode》

為了回饋各位粉絲，禮尚往來，給大家準備了一條多年積累下來的優質資源，包括 學習視訊、面試資料、珍藏電子書等

怎麼領取請大家自己找，尋寶遊戲現在開始。

找不到可以評論留言，一條就會注意到你。

如果還不行，請私信我。