为什么我的限制超过了前k个常见问题[LEETCODE]？
为什么我的限制超过了前k个常见问题[LEETCODE]？
提问于 2019-03-05 07:30:37
对于Leetcode的前k个常见问题，我有以下代码。
允许的时间限制复杂度小于o(nlogn)，其中n是数组大小
我的大型O不是o(n)的复杂性吗？如果是这样，为什么我仍然超过了时间限制？
def topKFrequent(self, nums, k):
output = {}
outlist = []
for item in nums:
output[item] = nums.count(item)
max_count = sorted(output.values(),reverse= True)[:k]
for key,val in output.items():
if val in max_count:
outlist.append(key)
return (outlist)测试输入：数组1,1,1,2,2,3,1,1,1,2,2,3 k=2
测试输出： 1,2
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-03-05 07:37:08
您的解决方案是O(n^2)，因此：
for item in nums:
output[item] = nums.count(item)对于数组中的每一项，您都要遍历整个数组，以计算相同元素的数量。
而不是这样做，您可以通过迭代nums并在找到的每个项目的计数器上加1来获得O(n)中的计数。
最终的O(n log n)将来自sorted(output.values(), reverse=True)，因为每个通用排序算法(包括Timsort)都将是O(n log n)的。
Stack Overflow用户
发布于 2019-03-05 09:25:12
正如另一个答案提到的，您的计算是O(n^2)时间复杂度，这导致您的时间限制被超过。幸运的是，python在collections模块中附带了一个Counter对象，它将用经过良好优化的C代码完成另一个答案所描述的工作。这将降低O(nlogn)的时间复杂度。
此外，您可以通过使用最小堆技巧替换排序调用来降低O(nlogk)的时间复杂度。保留一个大小为k的最小堆，然后添加其他元素并逐个弹出最小堆，直到所有元素都已插入(在某个点或另一个点)。堆中保留的k是您的最大k值。
from collections import Counter
from heapq import heappushpop, heapify
def get_most_frequent(nums, k):
counts = Counter(nums)
counts = [(v, k) for k, v in counts.items()]
heap = counts[:k]
heapify(heap)
for count in counts[k:]:
heappushpop(heap, count)
return [k for v, k in heap]如果必须以任何特定的顺序返回元素，则可以按O(klogk)时间对k元素进行排序，这在总体上仍然会导致相同的O(nlogk)时间复杂度。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54993207
复制相关文章
相似问题