说一道排序题
最新回答
凤舞九天
2026-10-22 14:09:07
要解决“前K个高频元素”问题且不使用内置库，可以采用桶排序（Bucket Sort）的变种方法。以下是详细步骤和代码实现：
方法思路- 统计频率：首先遍历数组，使用字典统计每个数字出现的频率。
- 构建频率桶：创建一个列表，其中索引代表频率，值对应的是具有该频率的数字列表。
- 收集结果：从最高频率开始遍历桶，收集数字直到结果数量达到k。
这种方法利用了桶排序的思想，通过频率作为索引来组织数据，避免了直接对字典进行排序，从而提高了效率。
解决代码class Solution(object): def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ # 统计每个数字的频率 frequency_map = {} for num in nums: if num in frequency_map: frequency_map[num] += 1 else: frequency_map[num] = 1 # 创建桶，索引为频率，值为该频率的数字列表 max_freq = max(frequency_map.values()) if frequency_map else 0 buckets = [[] for _ in range(max_freq + 1)] for num, freq in frequency_map.items(): buckets[freq].append(num) # 从高频率到低频率收集数字 result = [] for i in range(len(buckets) - 1, 0, -1): for num in buckets[i]: result.append(num) if len(result) == k: return result return result代码解释- 统计频率：使用字典frequency_map来记录每个数字在数组nums中出现的次数。
- 构建频率桶：根据字典中的最大频率值max_freq，初始化一个长度为max_freq + 1的列表buckets。然后遍历字典，将数字根据其频率放入对应的桶中。
- 收集结果：从最高频率的桶开始遍历，将数字逐个加入结果列表result，直到收集到k个数字为止。
这种方法避免了直接使用内置的排序函数，通过桶排序的思想高效地解决了问题，时间复杂度主要取决于统计频率和遍历桶的过程，整体为O(n)，其中n是数组nums的长度。
热门标签
