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;
        }
    }
}