劍指 Offer 40. 最小的k個(gè)數(shù)

輸入整數(shù)數(shù)組 arr ，找出其中最小的 k 個(gè)數(shù)。例如，輸入4、5、1、6、2、7、3、8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1、2、3、4。

?

示例 1：

輸入：arr = [3,2,1], k = 2

輸出：[1,2] 或者 [2,1]

示例 2：

輸入：arr = [0,1,2,1], k = 1

輸出：[0]

?

這道好簡(jiǎn)單，隨手做一下

class?Solution:

????def?getLeastNumbers(self,?arr:?List[int],?k:?int)?->?List[int]:

????????arr.sort()

????????return?arr[0:k]

我靠發(fā)現(xiàn)我做法太屑了，原來(lái)是要考快排，緊急速學(xué)快排

class Solution:
? ?def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
? ? ? ?def quickSort(arr,l,r):
? ? ? ? ? ?if l>=r:return
? ? ? ? ? ?i=l
? ? ? ? ? ?j=r
? ? ? ? ? ?while i<j:
? ? ? ? ? ? ? ?while i<j and arr[j]>=arr[l]:j-=1
? ? ? ? ? ? ? ?while i<j and arr[i]<=arr[l]:i+=1
? ? ? ? ? ? ? ?arr[i],arr[j]=arr[j],arr[i]
? ? ? ? ? ?arr[l],arr[i]=arr[i],arr[l]
? ? ? ? ? ?quickSort(arr,l,i-1)
? ? ? ? ? ?quickSort(arr,i+1,r)
? ? ? ?quickSort(arr,0,len(arr)-1)
? ? ? ?return arr[:k]

?