215. 数组中的第K个最大元素

Difficulty
Medium
Tags
排序
URL
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
Star
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 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 <= 104
  • 104 <= nums[i] <= 104

法 1 快速排序

思路
正常排序然后返回 nums[-k] 肯定没错，但就绝对不是面试官想看到的。
更优的操作是 采用快速排序的分区函数，直接返回第L大的元素，然后不断的判断L和len(nums)-k的大小，进而不断的缩小搜索空间
题解
import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        target = len(nums) - k
        l, r = 0, len(nums)-1
        idx = self.partition(nums, l, r)
        while idx != target:
            if idx > target:
                r = idx - 1
            else:
                l = idx + 1
            idx = self.partition(nums, l, r)

        return nums[idx]
            

    def partition(self, nums, start, end):
        povit = random.randint(start, end)
        # 先交换 选中的值和末尾值
        nums[povit], nums[start] = nums[start], nums[povit]

        # 上面的步骤相当于是随机选择了哨兵
        povit = start
        # 再把小于哨兵的值放到最开始
        l = start 
        for r in range(start+1, end+1):
            if nums[r] < nums[povit]:
                l += 1
                nums[l], nums[r] = nums[r], nums[l]

        nums[l], nums[povit] = nums[povit], nums[l]

        return l
			
		# 上述划分函数是把小于 哨兵的值放在哨兵左边，当然也可以把小于等于的值放左边：
		def partition(self, nums, l, r):
        povit = random.randint(l, r)
        nums[povit], nums[l] = nums[l], nums[povit]
        i = l - 1
        for j in range(l, r+1):
            if nums[j] <= nums[l]:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]

        nums[l], nums[i] = nums[i], nums[l]
        return i