347. Top K Frequent Elements

Link

難易度 : Medium

這題給予一個整數陣列nums與一個正整數k，要求回傳所有出現頻率前k高的數字。

這個題目分兩個部分

1. 紀錄數字與對應的出現次數

我會先看一下題目的資料範圍，發現完全沒有提及nums[i]的範圍，那就沒辦法了不能使用預先建好的陣列來儲存，改以HashMap來記錄對應的次數。

2. 排序頻率前k高的結果

想法是將所有結果排序，並且取出前k個當作結果不是不行，只是題目有額外要求我們需要將時間複雜度實現小於O(nlogn)

這邊的第一種作法是使用heap，至於要使用maxheap或是minheap這邊可以思考一下?

maxheap雖然可以在最後可以保證每次poll的都是最大值，但是就變成整個head需要留存所有出現過的元素，因為幾乎沒辦法判斷之後出現的會不會都是某種特定元素，會導致要重複的對heap做排序
minheap可以保證每次poll的都是最小的，那麼事情就可以轉變成讓heap中保存最大的k個，只要超過k的容量，就將最小的拋出，這樣不僅保證了heap空間容量較小也不需要做過多的排序

    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            int[] result = new int[k];
            //使用map紀錄數字與出現次數
            HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

            for(int i=0;i<nums.length;i++) 
            {
                map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            }

            //使用minHeap讓每次超過k個元素時可以把出現次數最小的那個元素排除
            PriorityQueue<Map.Entry<Integer,Integer>> minHeap = new PriorityQueue<>((v1,v2)->v1.getValue()-v2.getValue());
            for(Map.Entry<Integer,Integer> entry : map.entrySet()) 
            {
                //將剛剛計入好的entry加入heap中
                minHeap.add(entry);

                //如果超過前k個的條件 則將出現次數最小的拋出不要了
                if(minHeap.size()>k) 
                {
                    minHeap.poll();
                }
            }

            for(int i=0;i<k;i++) 
            {
                result[i] = minHeap.poll().getKey();
            }
            return result;
        }
    }

第二種做法是在Discuss中看到的，具體思路如下

1. 使用HashMap紀錄key與對應的出現頻率
2. 使用長度nums.length+1的List陣列
   A. 陣列idnex表示出現頻率
   B. 陣列的各個List表示該出現頻率的所有key

    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            int[] result = new int[k];
            //使用map紀錄數字與出現次數
            HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

            //list陣列來記錄每個"出現次數"所包含的"數字" 出現次數用index表示
            List<Integer>[] bucket = new List[nums.length+1];

            for(int i=0;i<nums.length;i++) 
            {
                map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            }


            for(int key : map.keySet()) 
            {
                int counts = map.get(key);
                if(bucket[counts]==null) 
                {
                    bucket[counts] = new ArrayList<Integer>();
                }
                //將counts出現次數的list加入這個數字key
                bucket[counts].add(key);
            }

            //從最大的次數開始向前尋找 只找前k個
            for(int i=bucket.length-1,counts=0;i>=0&&counts<k;i--) 
            {
                if(bucket[i]!=null) 
                {
                    for(int key : bucket[i]) 
                    {
                        result[counts++] = key;
                    }
                }
            }

            return result;
        }
    }