基本思想

通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

實現原理

整個數組找基準正確位置，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面。

Partition函數

首先，先寫partition模板

def partition(nums, left, right):pivot = nums[left]#初始化一個待比較數據i,j = left, rightwhile(i < j):while(i<j and nums[j]>=pivot): #從后往前查找，直到找到一個比pivot更小的數j-=1nums[i] = nums[j] #將更小的數放入左邊while(i<j and nums[i]<=pivot): #從前往后找，直到找到一個比pivot更大的數i+=1nums[j] = nums[i] #將更大的數放入右邊#循環結束，i與j相等nums[i] = pivot #待比較數據放入最終位置 return i #返回待比較數據最終位置

快速排序

#快速排序 def quicksort(nums, left, right):if left < right:index = partition(nums, left, right)quicksort(nums, left, index-1)quicksort(nums, index+1, right)arr = [1,3,2,2,0] quicksort(arr, 0, len(arr)-1) print(arr)

topk切分

將快速排序改成快速選擇，即我們希望尋找到一個位置，這個位置左邊是k個比這個位置上的數更小的數，右邊是n-k個比該位置上的數大的數，我將它命名為topk_split，找到這個位置后停止迭代，完成了一次劃分。

def topk_split(nums, k, left, right):#尋找到第k個數停止遞歸，使得nums數組中index左邊是前k個小的數，index右邊是后面n-k個大的數if (left<right):index = partition(nums, left, right)if index==k:return elif index < k:topk_split(nums, k, index+1, right)else:topk_split(nums, k, left, index-1)

獲得前k小的數

#獲得前k小的數 def topk_smalls(nums, k):topk_split(nums, k, 0, len(nums)-1)return nums[:k]arr = [1,3,2,3,0,-19] k = 2 print(topk_smalls(arr, k)) print(arr)

獲取第k小的數

#獲得第k小的數 def topk_small(nums, k):topk_split(nums, k, 0, len(nums)-1)return nums[k-1] #右邊是開區間，需要-1arr = [1,3,2,3,0,-19] k = 3 print(topk_small(arr, k)) print(arr)

獲得前k大的數

#獲得前k大的數 def topk_larges(nums, k):#parttion是按從小到大劃分的，如果讓index左邊為前n-k個小的數，則index右邊為前k個大的數topk_split(nums, len(nums)-k, 0, len(nums)-1) #把k換成len(nums)-kreturn nums[len(nums)-k:] arr = [1,3,-2,3,0,-19] k = 3 print(topk_larges(arr, k)) print(arr)

獲得第k大的數

#獲得第k大的數 def topk_large(nums, k):#parttion是按從小到大劃分的，如果讓index左邊為前n-k個小的數，則index右邊為前k個大的數topk_split(nums, len(nums)-k, 0, len(nums)-1) #把k換成len(nums)-kreturn nums[len(nums)-k] arr = [1,3,-2,3,0,-19] k = 2 print(topk_large(arr, k)) print(arr)

只排序前k個小的數

#只排序前k個小的數 #獲得前k小的數O(n)，進行快排O(klogk) def topk_sort_left(nums, k):topk_split(nums, k, 0, len(nums)-1) topk = nums[:k]quicksort(topk, 0, len(topk)-1)return topk+nums[k:] #只排序前k個數字arr = [0,0,1,3,4,5,0,7,6,7] k = 4 topk_sort_left(arr, k)

只排序后k個大的數

#只排序后k個大的數 #獲得前n-k小的數O(n)，進行快排O(klogk) def topk_sort_right(nums, k):topk_split(nums, len(nums)-k, 0, len(nums)-1) topk = nums[len(nums)-k:]quicksort(topk, 0, len(topk)-1)return nums[:len(nums)-k]+topk #只排序后k個數字arr = [0,0,1,3,4,5,0,-7,6,7] k = 4 print(topk_sort_right(arr, k))

作者：jun-lin-w
鏈接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/ji-yu-kuai-pai-de-suo-you-topkwen-ti-jia-ylsd/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

猜你喜歡：👇🏻
?【Leetcode】幾種簡單的排序算法
?【Leetcode】二分法左側邊界右側邊界模板
?【Leetcode】島嶼問題（數量，周長，面積）

總結

以上是生活随笔為你收集整理的【Leetcode】大神总结的所有TopK问题模板（基于快速排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。