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

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

思路

快排中，每次排序确定一个元素的位置，不妨设该元素为x。x将左右区间分为两份，左区间的所有元素<=x,右区间的所有元素>=x，此时我们可以寻找第k大的元素在哪个区间，从而只对某个区间进行排序即可。

解题方法

从大到小快排，判断第k大的元素在哪一半区间，然后递归。

复杂度

时间复杂度: $O(N)$ 只需要递归一半，也就是递归搜索树的一条链，线性的

空间复杂度: $O(logN)$ 递归栈的开销，一共递归了$logN$次

Code

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick(nums, l, r, k):
            if l >= r: return nums[l]
            x = nums[l + r >> 1]
            i, j = l - 1, r + 1
            while i < j:
                while True:
                    i += 1
                    if nums[i] <= x: break
                while True:
                    j -= 1
                    if nums[j] >= x: break
                if i < j: nums[i], nums[j] = nums[j], nums[i]
            if j - l + 1 >= k: 
                return quick(nums, l, j, k)
            else: 
                x = k - (j - l + 1)
                return quick(nums, j + 1, r, x)
        
        return quick(nums, 0, len(nums) - 1, k)

原文地址：https://blog.csdn.net/qq_49821869/article/details/137460181

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！