Leetcode-347-前K个高频元素

Leecode-347-Top K Frequent Elements

思路：堆

题目描述

给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

Solution

• 这里题目描述中对时间复杂度做出了要求 ，需要在 O(n log n)的限制。

Solution : 粗暴排序法

• 最简单粗暴的思路就是 使用排序算法对元素按照频率由高到低进行排序，然后再取前 k 个元素。

• 可以发现，使用常规的诸如冒泡，选择，甚至快速排序都不满足要求，它们的时间复杂度要求必须优于O(nlogn)

• 时间复杂度：O(nlogn)，n 表示数组长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；接着，排序算法时间复杂度为 O(nlogn)；因此整体时间复杂度为 O(nlogn)。

• 空间复杂度：O（n） ，需要Map来存储n个键值对

接下来我们介绍遇到TopK问题最常用的方法：最大堆或者最小堆

本题使用的是最小堆

Solution : 最小堆

• 题目最终需要返回的是前k个频率最大的元素。可以想到借助堆这种数据结构，对于k频率之后的元素不用再去处理，进一步优化时间复杂度
• 举个例子：

具体的操作流程为：

• 借助哈希表来建立数字和其出现次数之间的映射，遍历一遍数组统计元素的频率

• 维护一个元素数目是 k 的最小堆

• 每次都将新的元素和堆顶元素（堆中频率最小的元素）进行比较

• 如果新的元素频率比堆顶的元素大，则弹出堆顶的元素，将新的元素添加进堆中

• 最终，堆中的K个元素就是前 k 个高频元素。

Java

Solution :

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // 统计每个元素出现的次数，元素为键，元素出现的次数为值
        Map<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);
            }
        }


        // 构造最小堆
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });

        // 每次将新的元素和堆顶元素（堆中频率最小的元素）进行比较
        for (Integer key : map.keySet()) {
            if (pq.size() < k){
                pq.add(key);
            }else if (map.get(key) > map.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }

        // 取出最小堆中的元素
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty()){
            res.add(pq.remove());
        }
        return res;
    }
}

简便写法

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计每个元素出现的次数，元素作为key，元素出现的次数作为值
        Map<Integer,Integer> map = new HashMap<>();
        
        for(int num: nums){
            map.put(num,map.getOrDefault(num,1) + 1);
        }

        // 2. 构造一个k个元素的小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> map.get(a) - map.get(b));

        // 3.每次将新的元素和堆顶的元素比较（堆中频率最小的元素进行比较）
        for(Integer key:map.keySet()){
            if(pq.size() < k){
                pq.offer(key);
            }else if(map.get(key) > map.get(pq.peek())){
                pq.remove();
                pq.offer(key);
            }
        }

        // 4. 取出最小堆的元素
        int[] res = new int[k];
        int index = 0;
        while(!pq.isEmpty()){
            res[index++] = pq.remove();
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(nlogk)，n 表示数组的长度。首先，遍历一遍数组统计元素的频率，这一系列操作的时间复杂度是 O(n)；接着，遍历用于存储元素频率的 map，如果元素的频率大于最小堆中顶部的元素，则将顶部的元素删除并将该元素加入堆中，这里维护堆的数目是 k，所以这一系列操作的时间复杂度是O(nlogk) 的；因此，总的时间复杂度是 O(nlog⁡k)。
• 空间复杂度：O(n)，最坏情况下（每个元素都不同），map 需要存储 n 个键值对，优先队列需要存储 k 个元素，因此，空间复杂度是 O(n)。

手动使用小顶堆实现TopK

public class HeapSort{
    public static void heapSort(int[] tree,int n) {
        buildHeap(tree, n);//第一步是将得到的数组构建成小顶堆
        for(int i = n-1;i>=0;i--) {
            swap(tree, i, 0);//第一次构建完小顶堆之后，要进行第一个数和最后一个树的交换
            //交换完之后，最上面的数就不是最小数了，因此只需要对最上面的数，进行一个树的调整即可
            //所以，我们使用的时adjustTree而不是buildHeap
            adjustTree(tree, i, 0);//这里解释一下，这参数的含义：之所以将i当做数组的长度，
            //是因为我们将第一个数和最后一个数交换之后，就已经把最小的数放在了数组最后，进行
            //树调整的时候，就不需要管最后一个数字了。而0就是因为交换之后需要进行节点调节的那个节点
            //换到了第一个位置
        }
    }        
    /*
     * 这个函数写完之后，就可以将任意一个数组，构建成小顶堆了，构建完小顶堆之后，就要进行堆排序了
     */
    public static void buildHeap(int[] tree,int n) {
        for(int i = (n-1)/2;i>=0;i--) {//i从最后一个子节点的父节点开始，所以i = (n-1)/2
            adjustTree(tree, n, i);
        }
    }
    //利用adjustTree和swap两个函数，可以针对某一个父节点，进行调节。接下来，解决当整个树是
    //乱序的，将一个树构建成一个小顶堆。思路是这样的：从最后一个子节点的父节点开始调节，往上走。
    //不断重复，每往上一个父节点，父节点的下标就减一，可以将adjustTree和swap函数放进一个for循环
    //就是上面的for循环
    /*
     * 表示从某一个节点开始，调整一次树，使之成为堆，其中i表示某一个节点的下标
     */
    public static void adjustTree(int[] tree,int n,int i) {
        if(i>=n) {//这是递归头。
            return;
        }
        //首先确定i节点的左右两个孩子的下标
        int c1 = 2*i+1;
        int c2 = 2*i+2;
        //接下来，在这三个值中，找出最小值
        int max = i;//先假设最小值为这个父节点
        if(c1<n && tree[c1]>tree[max]) {//要保证c1不会出界
            max = c1;
        }
        if(c2<n && tree[c2]>tree[max]) {//保证c2不会出界  c2<n
            max = c2;
        }
        //经过上面的条件判断，就可以将最小值的下标保存到max中了，如果最小值max就是i，也就是
        //父节点最小，就不用调整，但是如果父节点不是最小，就要进行交换了
        if(max!=i) {
            swap(tree,max,i);
            adjustTree(tree,n,max);//交换之后，将父节点下放一级，就有可能会破坏下一层结构，
            //所以，递归调用adjustTree.使用递归之后，就要添加递归头了
        }              
    }
    private static void swap(int[] tree, int i, int j) {
        int temp = tree[i];
        tree[i] = tree[j];
        tree[j] = temp;
    }
}

public class TopK {
    public static void main(String[] args) {

        int[] data = new int[]{1, 3, 4, 2, 8, 9, 5, 6, 7, 32, 56, 23, 87, 32};//原始数据

        int[] topk = topK(data, 5);//调用topK方法，返回前k大的数组，返回的数组并不是有序的，而是一个小顶堆，如果想返回一个有序的，可以调用上面HeapSort类中的heapSort方法

        for (int i = 0; i < topk.length; i++) {//循环输出小顶堆
            System.out.println(topk[i]);
        }
    }

    public static int[] topK(int[] data, int k) {
        int[] topk = new int[k];//根据传进来的K创建长度为k的数组

        for (int i = 0; i < k; i++) {
            topk[i] = data[i];//先将源数据的前k个的数赋值给topK数组
        }

        HeapSort.buildHeap(topk, k);//对这个topK数组进行一次最小堆的构建。

        for (int i = k; i < data.length; i++) {//从源数据的第K个数开始循环，如果循环的数比堆顶元素还小，直接pass，
            // 如果比堆顶元素要大，就将此数放在堆顶，同时进行一次以它为起始点的树的调整。
            int temp = data[i];
            if (topk[0] < temp) {
                topk[0] = temp;
                HeapSort.adjustTree(topk, k, 0);
            }
        }
        return topk;
    }
}

打赏