leetcode347_前K个高频元素

题目描述：

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例1：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例2：

输入: nums = [1], k = 1
输出: [1]

说明：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 $O(n log n)$, n 是数组的大小。

解法一：小顶堆

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1,1,1,2,2,3};
        int k = 2;
        System.out.println(solution.topKFrequent(nums1, k));    //[1, 2]
    }
    public List<Integer> topKFrequent(int[] nums, int k) {    //返回值是一个列表List
        HashMap<Integer, Integer> count = new HashMap();
        for (int n: nums) {
            count.put(n, count.getOrDefault(n, 0) + 1);    // count.getOrDefault(n, 0)+1) 
        }
        // init heap 'the less frequent element first' 小顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2));
        // keep k top frequent elements in the heap
        for (int n: count.keySet()) {	//key的集合
            heap.add(n);    //这里的add是根据key对应的值大小去插入的，最终得到小顶堆
            if (heap.size() > k) {
                heap.poll();
            }
        }
        List<Integer> top_k = new LinkedList();    //LinkedList底层是通过双向链表实现的
        while (!heap.isEmpty()) {
            top_k.add(heap.poll());
        }
        Collections.reverse(top_k);
        return top_k;
    }
}

复杂度分析

时间复杂度：$O(Nlogk)$。遍历一遍数组统计元素的频率的时间复杂度是 O(N)，建堆和输出的复杂度是 O(Nlog(k))。因此总复杂度为 O(N+Nlog(k))=O(Nlog(k))。

空间复杂度：$O(N)$，存储哈希表的开销。最坏情况下（每个元素都不同），map 需要存储 n 个键值对，优先队列需要存储 k 个元素，因此，空间复杂度是 O(n)。根据复杂度分析，方法对于小 k 的情况是很优的。但是如果 k 值很大，我们可以将算法改成删除频率最低的若干个元素。

解法二：桶排序法

首先依旧使用哈希表统计频率，统计完成后，创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可。

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1,1,1,2,2,3};
        int k = 2;
        System.out.println(solution.topKFrequent(nums1, k));    //[1, 2]
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList();    //返回值res是一个数组，其长度等于k
        // 使用哈希表（字典），统计每个元素出现的次数，元素为键，元素出现的次数为值
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            }
            else {
                map.put(num, 1);
            }
        }
        //桶排序：获取出现的次数作为下标
        //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
        List<Integer>[] list = new List[nums.length+1];    //list最大的长度是当输入的所有数字都一样时的长度加1
        for(int key : map.keySet()){
            int i = map.get(key);    // 获取出现的次数作为下标
            if(list[i] == null){
               list[i] = new ArrayList();  //这里是一个数组,因为可能有多个数字出现的次数是一样的
            }
            list[i].add(key);
        }
        // 倒序遍历数组获取出现顺序从大到小的排列
        for(int i = list.length - 1;i >= 0 && res.size() < k;i--){    //返回值res是一个数组，其长度等于k
            if(list[i] == null) continue;
            res.addAll(list[i]);    //存入的是一个数组，所以用addAll()而非add()
        }
        return res;
    }
}

复杂度分析

时间复杂度：O(n) ，n 表示数组的长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；桶的数量为 n+1，所以桶排序的时间复杂度为 O(n)；因此，总的时间复杂度是 O(n)。

空间复杂度：O(n) 。