有用建站宝盒做网站的吗,网站开发研究前景,做网站推广怎么做,网站建设2018需要什么题目#xff1a;
给定一个非空的整数数组#xff0c;返回其中出现频率前 k 高的元素。
示例 1:
输入: nums [1,1,1,2,2,3], k 2输出: [1,2]
示例 2:
输入: nums [1], k 1输出: [1]
提示#xff1a;
你可以假设给定的 k 总是合理的#xff0c;且 1 ≤ k ≤ 数组中…题目
给定一个非空的整数数组返回其中出现频率前 k 高的元素。
示例 1:
输入: nums [1,1,1,2,2,3], k 2输出: [1,2]
示例 2:
输入: nums [1], k 1输出: [1]
提示
你可以假设给定的 k 总是合理的且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的。你可以按任意顺序返回答案。
思路
主要用了大小顶堆的思想自己也是头一次接触网上看了相关视频和资料才有所了解建议大家先网上查阅资料。
我们要用小顶堆因为要统计最大前k个元素只有小顶堆每次将最小的元素弹出最后小顶堆里积累的才是前k个最大元素。
代码实现
import heapq # 需要注意 heapq的用法有所不同
class Solution:def topKFrequent(self, nums: List[int], k: int) - List[int]:my_dict {}for i in range(len(nums)):my_dict[nums[i]] my_dict.get(nums[i], 0) 1stack []for key, value in my_dict.items(): # 只有item()才能取出字典里的key和valueheapq.heappush(stack, (value, key)) # 是按value来给stack排序所以value要放前面。heapq.heappush的用法就是这样 在括号里面加要操作的目标和进堆的值if len(stack) k:heapq.heappop(stack) res [0] * kfor i in range(k-1, -1, -1):res[i] heapq.heappop(stack)[1] # heapq.heappop(stack)[1]是取出第二个元素也就是key值return res
时间及空间复杂度
时间复杂度: O(nlogk)空间复杂度: O(n)
