力扣215-数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣LeetCode给定整数数组nums和整数k请返回数组中第**k**个最大的元素。请注意你需要找的是数组排序后的第k个最大的元素而不是第k个不同的元素。你必须设计并实现时间复杂度为O(n)的算法解决此问题。示例 1:输入:[3,2,1,5,6,4],k 2输出:5示例 2:输入:[3,2,3,1,2,4,5,5,6],k 4输出:4提示1 k nums.length 105-104 nums[i] 104第 K 大元素在排序数组中的下标为 n - k所以本题变为随机选某个数将该数放在它应该在的位置如果这个位置刚好等于 n - k那么就返回此时由于这个数称之为 pivot已经在它应该在的位置了也就意味着 pivot 左侧一定都是比它小的数右侧一定都是比它大的数只不过不一定按顺序排列但是它的的确确已经在它应该在的位置了。如果这个位置比 n - k 大说明下标为 n - k 的元素一定在 pivot 的左侧因为第 K 大元素在从小到大排列的数组中的下标刚好为 n - k此时 pivot 的位置在 n - k 右侧显然要找的元素在 pivot 左侧因为左侧都是比它小的。因此接下来在左侧数组中随机选一个数把它放到它应该在的地方即可。如果 pivot 的位置比 n - k 小那么就在右侧数组中找即可。我们暂且称这个“在某个区间内选出随机数并将其放在它在这个区间中应该在的位置”的操作为 prp(Put it to the Right Place)因为要看 pivot 的位置与 n - k 谁大谁小因此可以确定prp 的返回值应当是 pivot 的下标。同时也可以写出 findKthLargest 的流程def findKthLargest(self, nums: List[int], k: int) - int: n len(nums) target_index n - k left, right 0, n - 1 while True: i self.prp(nums, left, right) if i target_index: # 找到第 K 大元素 return nums[i] elif i target_index: # pivot 已经在正确的下标但这个下标仍然比 n - k 要小 # 由于 pivot 的右侧都比它大而第 K 大元素在正确的位置时它的位置 n - k 在 pivot 右侧 # 所以第 K 大元素一定比 pivot 大因此去右侧数组找 pivot left i 1 else: right i - 1下一步完成 prp 函数1.在[left, right]中选出一个随机数作为 pivot其下标为 i2.交换nums[i]和nums[left]因为我们的目的是在[left, right]中把比 pivot 小的放在它左边比 pivot 大的放在它右边所以只需要记录 pivot 的值就行了。将 pivot 移出需要处理的数组部分这样就不需要在遍历这部分的时候单独处理遍历到 pivot 的逻辑了3.交换之后pivot leftpivot 已经远离了战场。令i left 1, j right[i, j]才是要遍历并处理的部分进入循环。循环逻辑为(a) 如果 i 不在 j 右侧且nums[i]比 pivot 小i 右移一格。因为我们本就希望把比 pivot 小的放在它左边。否则不动严格小于避免数组各元素均相同的情况下退化到O(n^2)(b) 如果 i 不在 j 右侧且nums[j]比 pivot 大j 左移一格理由同上为什么条件之一是 “ i 不在 j 右侧” 而不是 “ i 在 j 左侧”即为什么i j依然可以成为继续移动的必要条件之一假设 i 在 遇见 j 之前就停下来那么令 i 停下来的理由是什么是nums[i] pivot如果在 j 移动到了 i这个时候j i不进入循环。此时下标 j 就是 pivot 在[left 1, right]中的正确位置但是如果交换nums[left]与nums[j]由于 j 与 i 重合i 停下来的理由是nums[i]比 pivot 大所以此时nums[j]比 pivot 大那就相当于把一个比 pivot 大的数换到了它的左边这显然是不合理的能不能交换nums[left]和nums[j - 1]呢不合适因为如果 left 和 right 均为 0那 j - 1 就越界了所以要返回 j(a) (b) 两个循环的共同条件应该是i j而不是i j(c) i 和 j 探索完毕后如果 i 和 j 重叠或者 i 去到了 j 右侧break因为 j 右边的必然比 pivot 大i 左边的必然比 pivot 小现在两个重叠或者 j 在 i 左侧说明已经可以确定 pivot 的正确位置(d) 如果 i 和 j 在碰面之前就都停下来了说明此时nums[i] pivotnums[j] pivot但 i 还在 j 右侧一个左边的数比右边的数大这不是我们想要的结果因此交换nums[i]和nums[j]然后下一轮循环在[i 1, j - 1]里进行处理因为此时 i 及其左边的元素已经比 pivot 小了j 及其右边的元素已经比 pivot 大了因为比 pivot 小是 i 前进的动力比 pivot 大是 j 回退的动力。接下来进一步让 i 和 j 靠近就能让[i 1, j - 1]中比 pivot 大的都往右走比 pivot 小的都往左走(e) 循环结束后交换nums[left]和nums[j]上文已经说了理由(f) 返回 j即下标 j 就是 pivot 应该待的位置关于为什么不能是i j还有一个原因见灵神举的例子来看一个例子 nums[2,1,3]pivot2。左指针 i1 移动到 i2右指针 j2 因为不满足 i j 的条件无法移动。此时我们交换 2 和nums[j]3得到[3,1,2]返回 j2。然而 j2 左侧有大于 pivot2 的元素划分失败。如果写成 i j那么最终 i2j1。此时我们交换 2 和nums[j]1得到[1,2,3]返回 j1。这样的划分就是正确的。作者灵茶山艾府链接215. 数组中的第K个最大元素 - 力扣LeetCode来源力扣LeetCode著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。class Solution: def prp(self, nums: List[int], left: int, right: int) - int: i randint(left, right) pivot nums[i] nums[i], nums[left] nums[left], nums[i] i, j left 1, right while True: while i j and nums[i] pivot: i 1 while i j and nums[j] pivot: j - 1 if i j: break nums[i], nums[j] nums[j], nums[i] j - 1 i 1 nums[left], nums[j] nums[j], nums[left] return j def findKthLargest(self, nums: List[int], k: int) - int: n len(nums) target_index n - k left, right 0, n - 1 while True: i self.prp(nums, left, right) if i target_index: # 找到第 K 大元素 return nums[i] elif i target_index: # pivot 已经在正确的下标但这个下标仍然比 n - k 要小 # 由于 pivot 的右侧都比它大而第 K 大元素在正确的位置时它的位置 n - k 在 pivot 右侧 # 所以第 K 大元素一定比 pivot 大因此去右侧数组找 pivot left i 1 else: right i - 1分析一下时间复杂度第一次走 prp有 n - 1 个数除 pivot 外要被遍历到复杂度为 n设数组长度为 n 走完第一次后要么选左边要么选右边所以可以得到递推公式如果两边都递归那么就会变成将展开进一步展开最终即而所以即时间复杂度为 O(n) 级别