[leetcode/lintcode 題解] 算法面試高頻題詳解： 主元素 III

描述

給定一個整型數組，找到主元素，它在數組中的出現次數嚴格大于數組元素個數的1/k。

數組中隻有唯一的主元素

線上評測位址：

領扣題庫官網

樣例1
輸入: [3,1,2,3,2,3,3,4,4,4] and k=3, 
輸出: 3.           

樣例2
輸入: [1,1,2] and k=3, 
輸出: 1.           

挑戰

要求時間複雜度為O(n)，空間複雜度為O(k)

算法：hashmap

當一個數的出現次數大于等于元素總數除以k向上取整時說明找到答案

将所有數字都用map存下來，并存下出現次數

周遊這個map，找到次數大于總數k分之一的元素

複雜度分析

• 時間複雜度O(n)
  • n為數組大小
• 空間複雜度O(n)

代碼

public class Solution {
    /*
     * @param nums: a list of integers
     * @return: The majority number that occurs more than 1/3
     */
    public int majorityNumber(List<Integer> nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int n = nums.size();
        if(n == 0){
            return -1;
        }
        int count = n/k + 1;
        //周遊nums
        Iterator it = nums.iterator();
        while(it.hasNext()){
            Integer tmp = (Integer)it.next();
            if(map.containsKey(tmp)){
                int m = (int)map.get(tmp) + 1;
                map.put(tmp, m);
                // 判斷是否大于等于k分之一
                if(m >= count){
                    return tmp;
                }
            }
            else{
                map.put(tmp, 1);
            }
        }
        return nums.get(0);
    }
}           

更多題解參考：

九章官網solution