前 K 个高频元素

难度:

标签:

题目描述

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

示例 1:

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

示例 2:

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

提示：

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

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

代码结果

运行时间: 20 ms, 内存: 19.3 MB

/*
 * 思路：
 * 1. 使用流的方式统计每个数字的出现频率。
 * 2. 将频率统计结果转换为一个流，按频率排序后取前k个元素。
 */
 
import java.util.*;
import java.util.stream.Collectors;
 
public class TopKFrequentElementsStream {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计每个元素的频率
        Map<Integer, Integer> frequencyMap = Arrays.stream(nums)
            .boxed()
            .collect(Collectors.toMap(num -> num, num -> 1, Integer::sum));
 
        // 使用流的方式取频率最高的k个元素
        return frequencyMap.entrySet().stream()
            .sorted((a, b) -> b.getValue() - a.getValue())
            .limit(k)
            .map(Map.Entry::getKey)
            .mapToInt(Integer::intValue)
            .toArray();
    }
}

解释

方法:

该题解的思路是先用哈希表统计每个元素出现的频率，然后用小顶堆维护前 k 个高频元素。具体步骤如下： 1. 使用哈希表 map_fre 统计数组 nums 中每个元素出现的频率。 2. 创建一个小顶堆 pri_que，遍历哈希表中的键值对，将 (频率, 元素) 二元组插入堆中。 3. 在插入过程中，如果堆的大小超过 k，则弹出堆顶元素，保证堆中始终维护前 k 个高频元素。 4. 遍历完哈希表后，堆中剩下的就是前 k 个高频元素，将它们按照频率从高到低的顺序弹出并存入结果数组中。 5. 返回结果数组。

时间复杂度:

O(n log k)

空间复杂度:

O(n)

代码细节讲解

🦆

在算法中，哈希表`map_fre`用于统计每个元素的频率，如果数组`nums`中的所有元素都相同，哈希表的大小是否仍然为`n`？

▷

如果数组`nums`中的所有元素都相同，那么哈希表`map_fre`中将只有一个键值对，即这个重复元素及其总出现次数。因此，哈希表的大小为1，而不是`n`。

🦆

在堆`pri_que`中，元素是以`(频率, 元素)`的形式存储，这种存储方式是否支持在有相同频率的情况下，正确地保持元素的比较和弹出顺序？

▷

在Python中的小顶堆（使用`heapq`），当元素的第一关键字（在本例中是频率）相同时，它会使用元素的第二关键字进行比较（在本例中是元素本身）。因此，若频率相同，小顶堆会根据元素值大小进行排序。这种方式确实支持在频率相同的情况下，根据元素值的顺序来决定谁先被弹出。不过，这并不会影响题目的解决方法，因为题目只关心频率高低，对于频率相同的元素，并未要求特定的排序顺序。

🦆

算法最终返回的结果数组`result`是如何保证元素顺序与题目要求的前`k`高频的顺序一致的？是否存在因堆的性质导致的顺序问题？

▷

由于小顶堆`pri_que`维护的是前`k`高频元素，并且堆顶是这些元素中频率最低的，故在将元素从堆中移除并存入结果数组`result`时，需要逆序填充。这是因为堆弹出的顺序是从频率最低到最高，而题目要求是频率从高到低。因此，通过从结果数组的最后一个位置向前填充，可以确保最终数组的顺序与题目要求的前`k`高频的顺序一致。

相关问题

统计词频

写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。

为了简单起见，你可以假设：

words.txt只包括小写字母和 ' ' 。
每个单词只由小写字母组成。
单词间由一个或多个空格字符分隔。

示例:

假设 words.txt 内容如下：

the day is sunny the the
the sunny is is

你的脚本应当输出（以词频降序排列）：

the 4
is 3
sunny 2
day 1

说明:

不要担心词频相同的单词的排序问题，每个单词出现的频率都是唯一的。
你可以使用一行 Unix pipes 实现吗？

数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

根据字符出现频率排序

给定一个字符串 s ，根据字符出现的频率对其进行 降序排序 。一个字符出现的频率是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例 1:

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入: s = "cccaaa"
输出: "cccaaa"
解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入: s = "Aabb"
输出: "bbAa"
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

提示:

1 <= s.length <= 5 * 10⁵
s 由大小写英文字母和数字组成

分割数组为连续子序列

给你一个按 非递减顺序 排列的整数数组 nums 。

请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述两个条件：

每个子序列都是一个 连续递增序列（即，每个整数恰好比前一个整数大 1 ）。
所有子序列的长度至少为 3 。

如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

示例 2：

输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

示例 3：

输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。

提示：

1 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000
nums 按非递减顺序排列

前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

注意：

1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]

进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

最接近原点的 K 个点

给定一个数组 points ，其中 points[i] = [x_i, y_i] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x₁ - x₂)² + (y₁ - y₂)² ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案确保是唯一的。

示例 1：

输入：points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]
解释： 
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

示例 2：

输入：points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

提示：

1 <= k <= points.length <= 10⁴
-10⁴ < x_i, y_i < 10⁴

数据流中的移动平均值设计井字棋