Top k Largest Numbers

这道题的错也充分显示了基础知识不扎实导致的。
非常值得一记。

544. Top k Largest Numbers

Given an integer array, find the top k largest numbers in it.

Example

Given [3,10,1000,-99,4,100] and k = 3.
Return [1000, 100, 10].

思考过程：
O(N) 一遍nums是免不了的，所以关键就在于top k上。top k会被定义为一个数组。在本题的答案中，其实隐含了要求让所有的K个数都降序排列，但在这点上，题目并没有真正的要求。所以sorting是一个必要的过程。关键是怎么sort, 什么时候sort, 还有谁sort

暴力解法。
每次都遍历k数组，然后找到k数组中的最小数的index, 然后replace.
然后再在最后输出答案的时候，list.sort(reverse = True)
毫无疑问。time limit exceeded.
因为这样做的最差的时间复杂度为 O(N^2) 如果 K ~= len(nums)

聪明的解法。
Scenario: 想来，如果我的nums是一个streaming, 是不是可以让它在通过了某一个filter或者component的时候可以自动过滤出满足某一个criteria的值

priority_queue:
heapq:
heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero.

我的答案。complexity O(NLogN)

heapq的用法，

https://docs.python.org/2/library/heapq.html

https://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/

1 2 3 4 5 6 7 8 9 10 11 12 13

def topk(self, nums, k): # write your code here if len(nums) == k: nums.sort(reverse = True) return nums topkFilter = [-sys.maxint - 1] * k heapq.heapify(topkFilter) for n in nums: heapq.heappushpop(topkFilter, n) return heapq.nlargest(k, topkFilter)

看了geeksforgeeks的答案，实在又颠覆了三观。
https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

这个解法很有意思。

Method 5(Use Oder Statistics)
1) Use order statistic algorithm to find the kth largest element. Please see the topic selection in worst-case linear time O(n)
2) Use QuickSort Partition algorithm to partition around the kth largest number O(n).
3) Sort the k-1 elements (elements greater than the kth largest element) O(kLogk). This step is needed only if sorted output is required.

Time complexity: O(n) if we don’t need the sorted output, otherwise O(n+kLogk)

kth largest item in the list

利用quick sort里面partition的概念，唯一改了一小丢丢的是这次需要找到Partition的位置是固定的。只要找到这个位置以后就可以Output, 不需要像quick sort那要一脑门的走到底。。大哥走在前面，走着走着，跟着的小弟爬到半山腰说，头疼，高反，走不动了。然后就停在了海拔4000米的地方。这个4000米就是这个k.

最最根本回去还是算二分法的影射吧，当满足了某个条件的时候，便放弃不满足条件的部分。废话不多说了，我去implement一下下。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

def kthlargest(nums, k): if len(nums) == k: return nums elif len(nums) < k: return [] else: partition = kthlargestUtil(nums, k, 0, len(nums)-1) return nums[0:k] def kthlargestUtil(nums, k, start, end): pivot = nums[start] pstart, pend = start + 1, end while(pstart < pend): while nums[pstart] >= pivot and pstart < end: pstart += 1 while nums[pend] < pivot and pend > start: pend -= 1 if pstart < pend: nums[pstart], nums[pend] = nums[pend], nums[pstart] nums[start], nums[pend] = nums[pend], nums[start] found = pend - start if k - found == 0: return pend - 1 elif k > found: return kthlargestUtil(nums, k - found, pend, end) else: return kthlargestUtil(nums, k, start, pend - 1) test1 = [1, 1, 1, 1, 1] print kthlargest(test1, 2) test2 = [3,10,1000,-99,4,100] print kthlargest(test2, 3)

被坐标搞死了。。
The high lightened cord is due to solve the edge case
1. 全部都是一样的值
2. 选出来的那个pivot正好是左半边的最小值。