面试题40.最小的k数这里可以使用随机选择算法，平均时间复杂度为O(n)，最坏情况时间复杂度为O(n^2).此外，还可以使用更复杂的BFPRT算法。优点是平均时间复杂度和最坏情况时间复杂度都是O(n)。importrandomclass解决方案：defgetLeastNumbers(self,arr:List[int],k:int)->List[int]:ifnotarrork==0:return[]defpartition(l,r):pivot=arr[r]j=l-1foriinrange(l,r):如果arr[i]<=pivot:j+=1arr[i],arr[j]=arr[j],arr[i]arr[j+1],arr[r]=arr[r],arr[j+1]返回j+1deftopk(l,r,k):i=random.randint(l,r)arr[r],arr[i]=arr[r],arr[i]m=partition(l,r)ifm+1==k:returnifm+1
