leetcode學習筆記347 Top K Frequent Elements

leetcode學習筆記347

• 問題
• 思考
• • 方法1
  • 方法2

問題

Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
• It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

思考

前K個最頻繁出現的數. 那麼就是統計每個數字出現的次數, 然後根據次數進行降序排列, 得到前k個值.

方法1

時間複雜度 O ( n log ⁡ n ) O(n \log n) O(nlogn).

空間複雜度 O ( n ) O(n) O(n).

n : nums中出現的不重複的數字的個數

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 用map來存儲數字和對應的出現次數
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) 
            map.put(num, map.getOrDefault(num, 0) + 1);
        
        // 定義priorityQueue, 使用Pair的value的降序排列
        // Pair中的key是數字, value是數字出現的次數
        PriorityQueue<Pair<Integer, Integer>> que = new PriorityQueue<Pair<Integer, Integer>>(
                new Comparator<Pair<Integer, Integer>>() {
                    @Override
                    public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                        return Integer.compare(o2.getValue(), o1.getValue());
                    }
                });

        // 将資料防區queue
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            que.add(new Pair<Integer, Integer>(entry.getKey(), entry.getValue()));
        }
        
        // 傳回結果
        int[] res = new int[k];
        for (int i = 0; i < k; i++) 
            res[i] = que.poll().getKey();
        
        return res;
    }
}
           

方法2

在方法1中使用了标準的排序(快速排序). 對所有數字進行了排序, 其實我們隻需要對前k個數字進行排序就可以了.

時間複雜度 O ( k log ⁡ n ) O(k \log n) O(klogn).

空間複雜度 O ( n ) O(n) O(n).

n : nums中出現的不重複的數字的個數

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 用map來存儲數字和對應的出現次數
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums)
            map.put(num, map.getOrDefault(num, 0) + 1);
        
        // 用MyPiar來存儲數字和出現次數的對應關系,并放入一個數組中
        MyPair[] arr = new MyPair[map.size()];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet())
            arr[index++] = new MyPair(entry.getKey(), entry.getValue());

        // 對數組進行排序, 把次數最大的前k個元素放到前面
        // 在這裡需要自己實作排序算法
        sort(arr, k, 0, map.size() - 1);

        // 取出前k個元素
        int[] res = new int[k];
        for (int i = 0; i < k; i++)
            res[i] = arr[i].val;
        return res;
    }
    
    // 整體上是快速排序, 但是排在k位置之後的元素不用在進行排序
    private void sort(MyPair[] arr, int k, int left, int right) {
        if (left >= right)
            return;
        swap(arr, (left + right) / 2, right);
        int index = left;
        int countR = arr[right].count;
        for (int i = left; i < right; i++) {
            if (arr[i].count >= countR)
                swap(arr, i, index++);
        }
        swap(arr, index, right);
        if (index + 1 < k)
            sort(arr, k, index + 1, right);
        else if (index + 1 > k)
            sort(arr, k, left, index - 1);

    }

    private void swap(MyPair[] arr, int i, int j) {
        MyPair temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    class MyPair {
        int val;
        int count;

        public MyPair(int val, int count) {
            this.val = val;
            this.count = count;
        }
    }
}