select largest K number from unsorted array Python
heap:
take klog(n) time
code is as follow"
def siftdown(A, start, end): root = start child = 2 * root + 1 while child <= end: if child + 1 <= end and A[child] < A[child + 1]: child += 1 if A[root] < A[child]: A[child], A[root] = A[root], A[child] root = child else: return def heapify(A, count): start = (count - 2) / 2 while start >= 0: siftdown(A, start, count - 1) start = start -1 #def heapsort(A): # count = len(A) # heapify(A, len(A)) # end = count - 1 # while end > 0: # A[end], A[0] = A[0], A[end] # end -= 1 # siftdown(A, 0, end) # return A def topk(A, k): count = len(A) heapify(A, len(A)) end = len(A) - 1 while end > 0 and k > 0: A[end], A[0] = A[0], A[end] end -= 1 k -= 1 siftdown(A, 0, end) return A[end + s1:] #def drawmax(A): A = [3, 4, 5, 1, 2, 0] print topk(A, 3)
quick select take O(n) time find k values
import random def partition(num, pivotIndex, left, right): pivot = num[pivotIndex] num[pivotIndex], num[right] = num[right], num[pivotIndex] storeIndex = left for i in range(left, right): if num[i]< pivot: num[storeIndex], num[i] = num[i], num[storeIndex] storeIndex += 1 num[storeIndex], num[right] = num[right], num[storeIndex] return storeIndex def quickselect(num, k): left = 0 right = len(num) - 1 while True: pivotIndex = random.randint(left,right) pivotNewIndex = partition(num, pivotIndex,left, right) dist = pivotNewIndex - left if dist == k: return num[pivotNewIndex] elif dist > k: right = pivotNewIndex - 1 else: k -= (dist+1) left = pivotNewIndex + 1 num =[8, 9,0,1,2,3,6,7] print quickselect(num,3)
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。