【leetcode】347. 前k个高频元素

题目

347. 前k个高频元素

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

示例 1:

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

示例 2:

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

题解

1. 字典+排序

nlog(n)

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""dict_result = {}for num in nums:if num not in dict_result:dict_result[num] = 1else:dict_result[num] += 1sorted_list = sorted(dict_result.items(), key=lambda item: item[1], reverse=True)result = []for i in range(k):result.append(sorted_list[i][0])return result

1. 字典+最小堆

nlog(k)

class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""# 字典：nlog(n)dict_result = {}for num in nums:if num not in dict_result:dict_result[num] = 1else:dict_result[num] += 1#对频率排序#定义一个小顶堆，大小为kpri_que = [] #小顶堆for key, freq in dict_result.items():# 最小堆heapq.heappush(pri_que, (freq, key))if len(pri_que) > k:heapq.heappop(pri_que)result = [0] * kfor i in range(k-1, -1, -1):result[i] = heapq.heappop(pri_que)[1]return result

• 统计频次：首先使用字典 dict_result 统计每个数字的频率。

• 最小堆：通过 heapq 模块来实现最小堆，堆中存储的是 (频次, 数字) 元组。

• 每次将一个 (freq, num) 元组插入堆中。如果堆的大小超过了 k，则移除堆顶元素（频率最小的元素）。这样堆中始终保存的是频率最高的 k 个元素。

• 结果提取：从堆中提取出 k 个数字，并返回这些数字。

• 时间复杂度：
  O(n log k)：遍历 nums 中的 n 个元素，每次操作堆的时间复杂度为 O(log k)，因此总时间复杂度为 O(n log k)。

heapq 是 Python 内置的一个模块，用于实现 堆队列算法（也称为优先队列）。该模块提供了一个基于列表的最小堆实现。最小堆是一个二叉堆，其中每个父节点的值都小于或等于其子节点的值，因此堆顶总是最小的元素。

主要功能： 最小堆：heapq 默认实现的是最小堆（即堆顶是最小的元素）。可以用它来管理优先级队列等问题，自动保持元素的排序。

• 堆排序：通过使用 heapq，可以高效地获取最小或最大元素。

• 支持堆操作：heapq 提供了用于堆操作的几种函数，最常用的包括：

  • heappush(heap, item)：将元素 item 添加到堆中，保持堆的性质。

  • heappop(heap)：弹出堆顶元素（即最小元素），并保持堆的性质。

  • heapify(list)：将一个列表转化为堆。

  • heappushpop(heap, item)：将元素 item 添加到堆中并弹出堆顶元素。

  • heapreplace(heap, item)：弹出堆顶元素，并将 item 添加到堆中。

最小堆的性质： 每个父节点的值都小于或等于其子节点的值，这使得堆顶元素始终是最小的元素。

在 heapq 模块中，堆是用列表实现的，列表的第一个元素始终是堆顶元素。