leetcode:排序

快速选择（Quickselect）

快速选择用于解决从无序列表里查找k-th元素，也叫Kth Element问题，解决方法有：

• 排序：

  • 对列表排序，直接取第k大的元素。

      def findKthLargest(self, nums: List[int], k: int) -> int:
              nums.sort()
              return nums[len(nums) - k]
    

  • 时间复杂度：O(nlogn)

  • 空间复杂度：O(1)

• 堆：

  • 维护大小为k的堆，最后取堆顶。

      def findKthLargest(self, nums: List[int], k: int) -> int:
              heap = []
              for num in nums:
                  heappush(heap, num)
                  if len(heap) > k:
                      heappop(heap)
              return heappop(heap)
    

  • 时间复杂度：O(nlogk)

  • 空间复杂度：O(k)

• 快速选择：

  • 快速选择和快速排序类似，本来也是有同一个人Tony Hoare提出，区别在于快速排序要列表所有元素排序，故要对partition后的列表pivot左右两侧递归，而快速选择只要找到k-th元素，因此只要递归pivot一侧。

      def findKthLargest(self, nums: List[int], k: int) -> int:
              def swap(nums, i, j):
                  nums[i], nums[j] = nums[j], nums[i]
            
              def partition(nums, left, right, pivotIndex) -> int:
                  #partion array and return the final pivot index
                  pivotValue = nums[pivotIndex]
                  swap(nums, pivotIndex, right) #move pivot to end
                  storeIndex = left 
                  for iter in range(left, right):
                      if nums[iter] < pivotValue:
                          swap(nums, storeIndex, iter)
                          storeIndex += 1
                  swap(nums, right, storeIndex) #move pivot to tis final place
                  return storeIndex
            
              def quickselect(nums, left, right, k) -> int:
                  #return the k-th smallest element of the list within left..right inclusive
                  #(i.e. left <= k <= right)
                        
                  if left == right: #the list only contains one element
                      return nums[left] # return the element
                  pivotIndex = randint(left, right) #select a pivotIndex
                  pivotIndex = partition(nums, left, right, pivotIndex)
                  if k == pivotIndex: #k is the k-th num
                      return nums[k]
                  elif k < pivotIndex: #the k-th num is less than the pivot
                      return quickselect(nums, left, pivotIndex-1, k)
                  else: # the k-th num is greater than the pivot
                      return quickselect(nums, pivotIndex+1, right, k)
              if len(nums) == 0:
                  return -1
              return quickselect(nums, 0, len(nums)-1, len(nums) - k)
    

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)

leetcode-215:Kth largest element in an array