LeetCode347.前 K 个高频元素

**LeetCode347: 前 K 个高频元素**

### 题目描述给定一个非空的整数数组 `nums` 和一个整数 `k`，返回出现次数超过 `k` 的顶级元素。

### 示例* 输入：`nums = [1,1,1,2,2,3]`, `k =2`
输出：`[1,2]`

* 输入：`nums = [1]`, `k =1`
输出：`[1]`

### 解决方案#### 方法一：哈希表和堆栈我们可以使用哈希表来存储元素及其出现次数，然后使用堆栈来维护前 K 个高频元素。

import heapqclass Solution:
 def topKFrequent(self, nums: List[int], k: int) -> List[int]:
 # 使用哈希表统计元素出现的次数 count = {}
 for num in nums:
 if num not in count:
 count[num] =1 else:
 count[num] +=1 # 使用堆栈维护前 K 个高频元素 heap = []
 for num, freq in count.items():
 heapq.heappush(heap, (-freq, num))
 # 返回前 K 个高频元素 return [num for _, num in heapq.nsmallest(k, heap)]

#### 方法二：哈希表和快速排序我们可以使用哈希表来存储元素及其出现次数，然后使用快速排序来维护前 K 个高频元素。

import randomclass Solution:
 def topKFrequent(self, nums: List[int], k: int) -> List[int]:
 # 使用哈希表统计元素出现的次数 count = {}
 for num in nums:
 if num not in count:
 count[num] =1 else:
 count[num] +=1 # 使用快速排序维护前 K 个高频元素 def quicksort(arr):
 if len(arr) <=1:
 return arr pivot = random.choice(arr)
 left = [x for x in arr if x[0] < -pivot[0]]
 middle = [x for x in arr if x[0] == -pivot[0]]
 right = [x for x in arr if x[0] > -pivot[0]]
 return quicksort(left) + middle + quicksort(right)
 # 返回前 K 个高频元素 sorted_count = quicksort(list(count.items()))
 return [num for _, num in sorted_count[:k]]

###代码注释* `count` 哈希表用于存储元素及其出现次数。
* `heapq.heappush(heap, (-freq, num))` 将元素及其出现次数推入堆栈中。
* `heapq.nsmallest(k, heap)` 返回前 K 个高频元素。
* `quicksort(arr)` 使用快速排序维护前 K 个高频元素。

###代码示例* 输入：`nums = [1,1,1,2,2,3]`, `k =2`
输出：`[1,2]`

* 输入：`nums = [1]`, `k =1`
输出：`[1]`

### 总结本题目要求返回前 K 个高频元素。我们可以使用哈希表和堆栈或快速排序来解决这个问题。代码注释和示例有助于理解解决方案的逻辑。