登录
  • #刷题

请问‌‌‍‍‌‍‍‌‍‌‍‍‌‍‍‍‍‍‍‌‍‌‍‍‍‍‍‌‍‌‌‌一道 stream k largest element的最优解

darrenchou8155
348
2
Given an infinite stream of integers, find the kth largest element at any point of time.

本题是从头开始依次找到第k个大的元素,看下例子就能看懂啦

Example:

输入 = [10, 20, 11, 70, 50, 40, 100, 5, .......]

k = 3

输出 = [*, *, 10, 11, 20, 40, 50, 50, ........]

这个是我的答案,我不知道是最优嘛,这个写的对不?

复杂度的话我这个是 time O(n * klogn) 嘛?

space: O(n)

import heapq[br][/br][br][/br]def kLargest(stream, k):[br][/br][br][/br] n = len(stream)[br][/br][br][/br] res = ['-' for _ in range(n)][br][/br][br][/br] if k >= n: return max(stream)[br][/br][br][/br] for i in range(k, n+1):[br][/br][br][/br]  maxs = heapq.nlargest(k, stream[​:i])[br][/br][br][/br]  res[i-1] = maxs[-1][br][/br][br][/br] return res[br][/br][br][/br]stream1 = [10, 20, 11, 70, 50, 40, 100, 5, 12,80][br][/br][br][/br]print(kLargest(stream1, 3))
2条回复
热度排序

发表回复