215. Kth Largest Element in an Array
题目来源
https://leetcode.com/problems/kth-largest-element-in-an-array/description/
题意分析
找出序列中第k大元素
题目思路
用快速选择算法求解，即随机选择数组中的一个数，进行划分，若划分的这个数恰好是第k大，那么返回结果。若不是，则对对应的子数组进行递归求解。
伪代码如下：
代码
import random
class Solution:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
return Solution().quick_select(nums,
0, len(nums), k-
1)
def quick_select(self, a, x, y, k):
if y-x<=
1:
return a[x]
rd = random.randint(x, y-
1)
a[rd],a[y-
1] = a[y-
1],a[rd]
v = a[y-
1]
j = x
for i
in range(x,y-
1):
if a[i]>v:
a[i],a[j] = a[j],a[i]
j+=
1
a[j],a[y-
1] = a[y-
1],a[j]
if k==j:
return a[j]
elif k<j:
return Solution().quick_select(a,x,j,k)
else:
return Solution().quick_select(a,j+
1,y,k)
结果
