利用快排做topk O(N)

利用快排做topk O(N)

首先是快排得到pivot的位置的过程

def quickSort2(data, left, right):
    low, high = left, right
    pivot = data[low]

    while low<high:

        while low<high and data[high] > pivot:
            high -= 1

        data[low] = data[high]

        while low<high  and data[low] < pivot:
            low += 1
        data[high] = data[low]

    data[low] = pivot
    return low


如果快排的话就是

def qs(data, left, right):
    if left<right:
        p = quickSort2(data, left, right)
        qs(data, left, p-1)
        qs(data, p+1, right)

    return data


得用快排可以做topk的

def topk(array, k):
    if k==0:
        return None
    if len(array) <=k:
        return array

    start, end = 0, len(array)-1
    index = quickSort2(array, start, end)

    ## 如果index刚好就是k的话,就直接返回前面的k个就可以了,但是如果不是的话,就继续找
    while index != k:
        if index > k:
            index = quickSort2(array, start, index)
        else:
            index = quickSort2(array, index+1 ,end)

    return array[:k]


相当于就是把整个数组扔进去,找到一个候选的index,如果index刚好就是k的话,就直接返回前面的k个,如果不是的话就看index的大小,如果比k大,说明要继续往前面找,即从start找到index,如果是比k小的话,就往后面找.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦