网页版淘宝_万网查询本地公网ip地址_市场调研分析报告怎么写_怎么做微信推广和宣传

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

思路

快排的变形-》快速选择

解题过程

根据快排（排序默认从小到大）的性质，每次递归后pivot将数组划分为两个区间，左区间所有的元素<=pivot，右区间所有元素>=pivot，此时右区间所有元素均>左区间。如果此时k<=len(左区间)，那么第k小的数从左区间找即可，直接递归左区间[l, j]，否则递归右区间[j+1, r]。题目要求的是第k大的数，所以需要满足左区间所有元素>=pivot，右区间<=pivot即可。

复杂度

• 时间复杂度: $O(n)$,由于每次递归将区间划分为两份，且只遍历某一半区间，所以时间复杂度为O(n+n/2+n/4…)≈O(2n)=O(n)
• 空间复杂度: $O(logn)$,数组长度是n，每次递归将数组划分为1/2，最多递归logn次，每次空间复杂度为O(1)，总的空间复杂度为O(logN)

Code

class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:def quick(l, r, k):# 快速选择 pvilot 这里是找第k个大的 所以要倒序if l >= r: return nums[l] # 只有一个元素或者没有pivot = nums[l+r>>1]i, j = l - 1, r + 1while i < j:while True:i += 1if nums[i] <= pivot: # 左边寻找<=x的breakwhile True:j -= 1if nums[j] >= pivot: # 右边寻找>=x的breakif i < j: nums[i], nums[j] = nums[j], nums[i]cnt = j - l + 1if cnt >= k:return quick(l, j, k)return quick(j+1, r, k-cnt)return quick(0, len(nums) - 1, k)