原题地址


3005.png

方法一 堆排序

此题其实用一个库函数sort就可以解决，但这显然不是本题的目的，所以我们要自己写一个算法来解决。

要找第k个大的元素，我们首先想到的就是堆排序。

正好我写过一个堆排序的文章，里面有详细的解释和代码

语雀内容

将堆排序的代码直接拿过来用就可以了。

Python代码

  1. def findKthLargest(self, nums: List[int], k: int) -> int:
  2.     def headAdjust(k, l):
  3.         i = 2 * k + 1  # i为k的左子结点
  4.         temp = nums[k]  # 暂存子树根结点
  5.         while i < l:
  6.             if i+1 < l and nums[i+1] > nums[i]:  # 让i指向k的左右结点中大的那个
  7.                 i += 1
  8.             if temp >= nums[i]: # 如果k的两个子节点都比k小
  9.                 break
  10.             else:
  11.                 nums[k] = nums[i]
  12.                 k = i
  13.             i = 2*i + 1  # 指向被调整过的那棵子树
  14.         nums[k] = temp
  15.     def buildMaxHeap(l):  # 建立大顶堆
  16.         for i in range(l//2-1, -1, -1):
  17.             headAdjust(i, l)
  18.     l = len(nums)
  19.     buildMaxHeap(l)  # 建堆
  20.     for i in range(0, k-1):
  21.         nums[0], nums[l-i-1] = nums[l-i-1], nums[0] # 输出大顶堆中最大元素
  22.         headAdjust(0, l-i-1)  # 调整堆
  23.     return nums[0]

时间复杂度O(nlogn)

空间复杂度O(logn)

buildMaxHeap的循环里调用headAdjust()算法时间复杂度为O(logn)，而headAdjust()里面使用了常数项变量temp，所以空间复杂度为O(logn)

方法二 快速排序

快速排序详解及代码

思路

我们知道快速排序是一个递归的过程，每次都会找出下标为pivlotpos的元素，使该下标左侧的所有元素都比nums[pivlotpos]小，右侧的都比它大。

我们可以利用这个特性，来找出第k大的元素。

只需对典型的快速排序算法做如下改动：

  • 第k大的元素，也就是数组从大到小排序后下标为k-1的那一个元素，所以当pivlotpos==k-1的时候，我们就找到了第k大的元素，为了方便，我们可以先让k--，这样到时候直接判断pivlotpos==k
  • 排序默认是从小到大排，我们改成从大到小排
  • 快排递归时默认先排左边子数组，再排右边子数组，我们改为条件判断。如果pivlotpos > k就排左侧子数组，反之排左侧子数组。

Python代码

  1. def findKthLargest(self, nums: List[int], k: int) -> int:
  2.     def Partition(low, high):
  3.         pivlot = nums[low]
  4.         while low < high:
  5.             while low < high and nums[high] <= pivlot:
  6.                 high -= 1
  7.             nums[low] = nums[high]
  8.             while low < high and nums[low] >= pivlot:
  9.                 low += 1
  10.             nums[high] = nums[low]
  11.         nums[low] = pivlot
  12.         return low
  14.     def quickSort(low, high):  # 对数组排序,找到第k大的数
  15.         if low < high:
  16.             pivlotpos = Partition(low, high)
  17.             if pivlotpos == k:
  18.                 return None
  19.             elif pivlotpos > k:
  20.                 quickSort(low, pivlotpos-1)
  21.             else:
  22.                 quickSort(pivlotpos+1, high)
  24.     if nums == []:
  25.         return -1
  26.     low, high = 0, len(nums)-1
  27.     k -= 1  # 表示要寻找排序后下标为k的那个数
  28.     quickSort(low, high)
  29.     return nums[k]

时间复杂度O(n)

这里我也不知道怎么推出来的，证明过程参考「《算法导论》9.2：期望为线性的选择算法」。

空间复杂度O(logn)

递归所用的栈空间的代价