347&692. 前K个高频元素&前K个高频单词

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

堆排序知识介绍请查看文章:LeetCode(347) 数组中的第 K 个最大元素(堆排序)

347. 前 K 个高频元素

本题来自 leetCode:347. 前 K 个高频元素[1]

题目详情

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

示例 1:

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

示例 2:

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

说明:

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

题目分析

  1. 首先统计各整数出现的频率;
  2. 维护一个元素数目为k的最小堆;
  3. 每次都将新的元素与堆顶元素(堆中频率最小的元素)进行比较;
  4. 如果新的元素的频率比堆顶端的元素大,则弹出堆顶端的元素,将新的元素添加进堆中;
  5. 最后堆中的k个元素即为前k个高频元素 (不一定是有序的,最后没有再排)

具体实现

class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {

// 统计各数出现的频率
Set<Map.Entry<Integer, Integer>> entrySet = count(nums);

Map.Entry<Integer, Integer>[] heap = new Map.Entry[k];
Iterator<Map.Entry<Integer, Integer>> iterator = entrySet.iterator();
for (int i = 0; i < k; i++) {
heap[i] = iterator.next();
iterator.remove();
}
// 排序
heapSort(heap, entrySet, k);
// 输出
return output(heap);
}

public Set<Map.Entry<Integer, Integer>> count(int[] nums) {
Map<Integer, Integer> table = new HashMap<>();

for (int num : nums) {
Integer count = table.getOrDefault(num, 0);
table.put(num, count + 1);
}

return table.entrySet();
}

public List<Integer> output(Map.Entry[] heap) {
List<Integer> topK = new ArrayList<>();
for (int i = 0; i < heap.length; i ++) {
topK.add((Integer)heap[i].getKey());
}
return topK;
}

/**
* 大根堆排序后的顺序为从小到大,只需要前k个元素有序
* @param heap
* @param entrySet
*/

public void heapSort(Map.Entry[] heap, Set<Map.Entry<Integer, Integer>> entrySet, int k) {
// 小根堆
BiPredicate<Map.Entry, Map.Entry> predicate = (a, b) -> (Integer) a.getValue() < (Integer) b.getValue();

// 先初始化最小堆
buildHeap(heap, k, predicate);

// 获取前k个频率高的值
for(Map.Entry entry : entrySet) {
// 小根堆堆顶的元素是最小值,若新加入的值大于堆顶堆顶元素,则置换
if(predicate.test(heap[0], entry)) {
heap[0] = entry;
// 由于堆结构发生了变化,需要继续对根元素nums[0]进行调整
adjustHeap(heap, 0, k, predicate);
}
}
}

/**
* 先初始化小根堆,使其满足所有非叶子节点:父节点的值小于子节点的值;
* @param heap
* @param length
*/

public void buildHeap(Map.Entry[] heap, int length, BiPredicate<Map.Entry, Map.Entry> predicate) {
//最后一个非叶子节点的位置为`n / 2 - 1`,从后向前,依次堆化
for(int i = (length >> 1) - 1; i >= 0; i --) {
adjustHeap(heap, i, length, predicate);
}
}

/**
* 堆化,使得父节点的值小于子节点的值
* @param heap 堆数组
* @param parent 待调整的非叶子节点
* @param length 调整范围
*/

public void adjustHeap(Map.Entry[] heap, int parent, int length, BiPredicate<Map.Entry, Map.Entry> predicate) {

// index位置节点的左子节点的位置为2 * i + 1
int left = (parent << 1) + 1;
// index位置节点的右子节点的位置为2 * i + 2
int right = (parent << 1) + 2;

// 存储父节点、左子节点、右子节点三者最小值的位置
int temp = parent;

// 比较父节点和左子节点的大小,
if(left < length && predicate.test(heap[left], heap[temp])) {
temp = left;
}

// 比较父节点和右子节点的大小
if(right < length && predicate.test(heap[right], heap[temp])) {
temp = right;
}

// 若父节点的值不是三者最小的
if(temp != parent) {
// 则交换和最小值子节点的值
swap(heap, parent, temp);
// 并继续调整子节点,使其堆化
adjustHeap(heap, temp, length, predicate);
}
}

/**
* 交换数组heap中i和j的值
* @param heap
* @param i
* @param j
*/

public void swap(Map.Entry[] heap, int i, int j) {
Map.Entry temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}

复杂度分析

时间复杂度O(n*log(k))。其中:

  1. 方法count()的复杂度是O(n)
  2. 方法heapSort()的复杂度是O(nlog(k))
  3. 方法output()的复杂度是O(k);

空间复杂度O(n),存储哈希表的开销。

692. 前 K 个高频单词

本题来自 LeetCode:692. 前 K 个高频单词[2]

题目详情

给一非空的单词列表,返回前  k  个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。
示例 1:

输入: ["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. 假定 k 总为有效值, 1≤ k≤集合元素数
  2. 输入的单词均由小写字母组成。

扩展练习:尝试以  O(nlogk)时间复杂度和O(n)空间复杂度解决。

题目分析

  1. 该题和347.前K个高频元素不同的地方在于输出结果需要按照单词出现频率由高到低排序,并且如果不同的单词有相同出现频率,按字母顺序排序。
  2. 改动点 1:对predicate的比较条件,增加相同频率时,按字母顺序排序;
  3. 改动点 2:获得前k个出现频率高的单词后,对这k个元素进行堆排列调整;

题目实现

class Solution {

public List<String> topKFrequent(String[] words, int k) {

// 统计各单词出现的频率
Set<Map.Entry<String, Integer>> entrySet = count(words);

Map.Entry<String, Integer>[] heap = new Map.Entry[k];
Iterator<Map.Entry<String, Integer>> iterator = entrySet.iterator();
for (int i = 0; i < k; i++) {
heap[i] = iterator.next();
iterator.remove();
}
// 排序
heapSort(heap, entrySet, k);
// 输出
return output(heap);
}

public Set<Map.Entry<String, Integer>> count(String[] nums) {
Map<String, Integer> table = new HashMap<>();

for (String num : nums) {
Integer count = table.getOrDefault(num, 0);
table.put(num, count + 1);
}

return table.entrySet();
}

public List<String> output(Map.Entry[] heap) {
List<String> topK = new ArrayList<>();
for (int i = 0; i < heap.length; i ++) {
topK.add((String)heap[i].getKey());
}
return topK;
}

/**
* 大根堆排序后的顺序为从小到大,只需要前k个元素有序
* @param heap
* @param entrySet
*/

public void heapSort(Map.Entry[] heap, Set<Map.Entry<String, Integer>> entrySet, int k) {
// 小根堆,同时根据首字母排序
BiPredicate<Map.Entry, Map.Entry> predicate = (a, b) -> {
if(a.getValue().equals(b.getValue())) {
String ka = (String) a.getKey();
String kb = (String) b.getKey();
return ka.compareTo(kb) > 0;
}
return (Integer) a.getValue() < (Integer) b.getValue();
};

// 先初始化最小堆
buildHeap(heap, k, predicate);

// 获取前k个频率高的值
for(Map.Entry entry : entrySet) {
// 小根堆堆顶的元素是最小值,若新加入的值大于堆顶堆顶元素,则置换
if(predicate.test(heap[0], entry)) {
heap[0] = entry;
// 由于堆结构发生了变化,需要继续对根元素nums[0]进行调整
adjustHeap(heap, 0, k, predicate);
}
}

// 调整堆,进入排序逻辑
for (int i = k - 1; i > 0 ; i --) {
swap(heap, 0, i);
adjustHeap(heap, 0, i, predicate);
}
}

/**
* 先初始化小根堆,使其满足所有非叶子节点:父节点的值小于子节点的值;
* @param heap
* @param length
*/

public void buildHeap(Map.Entry[] heap, int length, BiPredicate<Map.Entry, Map.Entry> predicate) {
//最后一个非叶子节点的位置为`n / 2 - 1`,从后向前,依次堆化
for(int i = (length >> 1) - 1; i >= 0; i --) {
adjustHeap(heap, i, length, predicate);
}
}

/**
* 堆化,使得父节点的值小于子节点的值
* @param heap 堆数组
* @param parent 待调整的非叶子节点
* @param length 调整范围
*/

public void adjustHeap(Map.Entry[] heap, int parent, int length, BiPredicate<Map.Entry, Map.Entry> predicate) {

// index位置节点的左子节点的位置为2 * i + 1
int left = (parent << 1) + 1;
// index位置节点的右子节点的位置为2 * i + 2
int right = (parent << 1) + 2;

// 存储父节点、左子节点、右子节点三者最小值的位置
int temp = parent;

// 比较父节点和左子节点的大小,
if(left < length && predicate.test(heap[left], heap[temp])) {
temp = left;
}

// 比较父节点和右子节点的大小
if(right < length && predicate.test(heap[right], heap[temp])) {
temp = right;
}

// 若父节点的值不是三者最小的
if(temp != parent) {
// 则交换和最小值子节点的值
swap(heap, parent, temp);
// 并继续调整子节点,使其堆化
adjustHeap(heap, temp, length, predicate);
}
}

/**
* 交换数组heap中i和j的值
* @param heap
* @param i
* @param j
*/

public void swap(Map.Entry[] heap, int i, int j) {
Map.Entry temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}

复杂度分析

时间复杂度O(n*log(k))。其中:

  1. 方法count()的复杂度是O(n)
  2. 方法heapSort()的复杂度是O(nlog(k))
  3. 方法output()的复杂度是O(k);

空间复杂度O(n),存储哈希表的开销。

参考资料

[1]

347. 前 K 个高频元素: https://leetcode-cn.com/problems/top-k-frequent-elements/

[2]

692. 前K个高频单词: https://leetcode-cn.com/problems/top-k-frequent-words/

原文始发于微信公众号(xiaogan的技术博客):347&692. 前K个高频元素&前K个高频单词