題目:
思路+代碼:
思路:
法一:調用python sorted 方法
時間複雜度:因為sorted也是使用餓快速排序實作餓,O(nlogn)
空間複雜度:額外需要空間O(logn)
法二:python 小頂堆實作
時間複雜度:n-k個數,維護小頂堆時間複雜度是O(logn), O(nlogk)
空間複雜度:小頂堆隻有k個數,O(logk)
法三:使用***,第一次确定的數看跟k比較;因為***每一次能确定基準的最終位置
時間複雜度:O(nlogn), 最差情況,每次劃分是最大值或者最小值,則需要劃分n-1次,每次需要n-i次關鍵字比較才能确定樞軸位置,此時時間複雜度是O(n x n)
空間複雜度:正常是log(n),但是最差情況時,需要存儲n-1個值
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
# 法一:調用python sorted 方法
if not arr: return
return sorted(arr)[:k]
# 法二:python 小根堆實作
if k == 0:
return list()
hp = [-x for x in arr[:k]] # 實際大的數在堆頂, hp[0]是堆頂元素
heapq.heapify(hp) # 把清單變成小頂堆,線性時間
for i in range(k, len(arr)):
if -hp[0] > arr[i]:
heapq.heappop(hp)
heapq.heappush(hp, -arr[i])
res = [-x for x in hp]
return res
# 法三:使用***,第一次确定的數看跟k比較;因為***每一次能确定基準的最終位置
def partition(self, nums, l, r):
pivot = nums[r]
i = l - 1
for j in range(l, r):
if nums[j] <= pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1], nums[r] = nums[r], nums[i + 1]
return i + 1
def randomized_partition(self, nums, l, r):
i = random.randint(l, r) # 随機确定基準
nums[r], nums[i] = nums[i], nums[r] # 基準和尾值交換
return self.partition(nums, l, r)
def randomized_selected(self, arr, l, r, k):
pos = self.randomized_partition(arr, l, r)
num = pos - l + 1
if k < num:
self.randomized_selected(arr, l, pos - 1, k)
elif k > num:
self.randomized_selected(arr, pos + 1, r, k - num)
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k == 0:
return list()
self.randomized_selected(arr, 0, len(arr) - 1, k)
return arr[:k]