topk:数组中的k项最大值//二维数组中的k项最大值

从n个数字中找出前top-k大的数字是常见的面试题,有如下几种解法:

暴力解法

这个基本思路类似于冒泡排序或者插入排序,以此遍历找到最大的数,最后返回k个最大的数,时间复杂度为 $O(NK)$

形如:

def getTopk(li,k):
    for i in range(k):
        start=0
        for j in range(start+1,len(li)):
            if(li[start]<li[j]):
                li[start],li[j]=li[j],li[start]
        start+=1
    return li[:start]

暴力解法不可取,基本就是跪了

快排解法

快排的平均时间复杂度为 $O(NlogN)$,利用快速排序的思路可以提高topk的效率

形如:

def getTopk(self,li,k):
    if(len(li)==0):
        return []
    left=[a for a in li[1:] if a>li[0]]
    right=[a for a in li[1:] if a<li[0]]
    print(left,right)
    if(len(left) > k):
        return self.getTopk(left,k)
    elif(len(left) == k):
        return left
    elif(len(left)+1 == k):
        return left+[li[0]]
    else:
        return left+[li[0]]+self.getTopk(right,k-1-len(left))
  1. 对快排算法中做如下改动:
  2. 左部分为大于首个数字li[0]的集合,若k小于左部分的长度,将左部分进入下一轮迭代;
  3. 若k等于左部分的长度,直接返回左部分;
  4. 若k等于左部分的长度加一,直接返回左部分加li[0];
  5. 若k打于左部分的长度加一,直接返回左部分加li[0]加右部分的迭代返回结果,右部分取前k-1-len(left)个;
  6. 返回最终的topk。

如上是改动的快速排序算法用于获得数组的前k项,时间复杂度最好是 $O(N)$,时间复杂度平均是 $O(KlogN)$,时间复杂度最坏是 $O(NK)$

堆排解法

堆排序的平均时间复杂度都为 $O(n*logn)$,它比快排好的地方是,快排在最坏的情况下(数组已有序)时间复杂度为 $O(n^2)$。

形如:

def getTopkInHeap(self,li,k):
    def headAdjust(li,start,end):#最大堆调整
        left=start*2+1
        while(left <= end):
            if(left+1 <= end and li[left] < li[left+1]):
                left+=1
            if(li[start] < li[left]):
                li[start],li[left] = li[left],li[start]
                start=left
                left=start*2+1
            else:
                break

    def heapSort(li,k,end):
        for i in range((end-1)//2,-1,-1):
            headAdjust(li,i,end)
        for i in range(end,end-k,-1):#取前k个调整到堆底
            li[i],li[0] = li[0],li[i]
            headAdjust(li,0,i-1)
        return li

    return li if k >= len(li) else heapSort(li,k,len(li)-1)[-k:]
  1. 定于headAdjust用于调整最大堆,将最大值移至堆顶;
  2. 定于heapSort堆排,首先初始化,调整堆;
  3. 以此取前k个元素调整到堆底,并重新调整堆;
  4. 返回后k个元素,若k大于数组长度,返回数组。

如上基于堆排算法修改的topk的时间复杂度为 $O(KlogN)$

堆排获取包含n堆数组的前k项

对于topk算法难度更进步的是,取n个堆中的最大的k个数,即二维数组的前k项。

形如:

def getTopkInNHeap(self,li,position,k):
    def headAdjust(li, position, start, end):#最大堆调整
        left=start*2+1
        while(left <= end):
            if(left+1 <= end and li[left][position[left]] < li[left+1][position[left+1]]):
                left+=1
            if(li[start][position[start]] < li[left][position[left]]):
                li[start],li[left] = li[left],li[start]
                position[start],position[left] = position[left],position[start]
                start=left
                left=start*2+1
            else:
                break

    def heapSort(li, position, k, end):
        for i in range((end-1)//2,-1,-1):
            headAdjust(li,position,i,end)
        topk=[]
        for i in range(k):
            print(li,position,end)
            topk.append(li[0][position[0]])
            position[0]+=1
            if(position[0]==len(li[0])):#调整
                li[end],li[0] = li[0],li[end]
                position[end],position[0] = position[0],position[end]
                end-=1
            headAdjust(li,position,0,end)
        return topk
    position=[0]*len(li)
    return [a for l in li for a in l] if k >= sum([len(l) for l in li]) else heapSort(li,position,k,len(li)-1)
  1. 定义position记录每堆被提取到的位置,定义headAdjust调整最大堆,将最大值移至堆顶,此时对应的是二维数组;
  2. 定义heapSort堆排,首先初始化最大堆;
  3. 依次取前k项(存在topk中),取走堆顶元素,调整对应的position值;
  4. 若堆顶对应的数组遍历完了,将其调整到堆底,修改end值;
  5. 调整最大堆,返回3;
  6. 返回topk,若k大于二维数组中的数字个数,返回展开的二维数组。
-------------本文结束你这么美,还坚持读完了-------------