每日一题：Leetcode-347 前K个高频元素

力扣题目

解题思路

java代码

力扣题目：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

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

示例 2:

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

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

解题思路：

算法原理：
这道题使用哈希表和桶排序的思想来找出给定数组中出现频率最高的 k 个元素。

思路：

1. 首先，使用哈希表 map 统计数组中每个元素出现的次数。
2. 然后创建一个桶数组 list ，桶的下标表示元素出现的次数，桶中存储出现次数相同的元素。
3. 最后，从桶数组的末尾开始向前遍历，将元素添加到结果列表 res 中，直到 res 的大小达到 k 。

代码分析：

• 先通过一个循环统计每个数字的出现次数，存入哈希表。
• 接着创建桶数组，并根据哈希表中的次数将数字放入对应的桶中。
• 最后通过倒序遍历桶数组，将符合条件的数字添加到结果列表中。

时间复杂度：

• 统计元素出现次数的时间复杂度为  ，其中 n 是数组 nums 的长度。
• 构建桶数组和填充桶的时间复杂度也为  。
• 最后的遍历桶数组的时间复杂度为  。
  综合起来，总的时间复杂度为  。

空间复杂度：

• 哈希表的空间复杂度为  。
• 桶数组的空间复杂度为  。
• 结果列表的空间复杂度为  。
  综合起来，总的空间复杂度为  。

java代码：

package org.example;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Leetcode347 {
    public static void main(String[] args) {
        Leetcode347 leetcode347 = new Leetcode347();
        Object[] ans = leetcode347.topKFrequent(new int[]{1,1,1,2,2,3}, 2).toArray();
        for (Object i : ans) {
            System.out.println(i);
        }
    }
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> res = new ArrayList();
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        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];
        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--){
            if(list[i] == null) continue;
            res.addAll(list[i]);
        }
        return res;
    }

}

更多详细内容同步到公众号，感谢大家的支持！

每天都会给刷算法的小伙伴推送明日一题，并且没有任何收费项