LeetCode 215. Kth Largest Element in an Array 时间复杂度(O(n))

时间复杂度(O(n))，思想：快排 

import random class Solution: def findKthLargest(self, nums: [int], k: int) -> int: k, re_start, re_end = k - 1, 0, len(nums) - 1 while True: p_direction, start, end = False, re_start, re_end _index = random.randint(start, end) nums[re_start], nums[_index] = nums[_index], nums[re_start] num_flag = nums[re_start] while start < end: if p_direction: if nums[start] < num_flag: p_direction, nums[end], end = False, nums[start], end - 1 else: start += 1 else: if nums[end] >= num_flag: p_direction, nums[start], start = True, nums[end], start + 1 else: end -= 1 nums[start] = num_flag if start == k: return nums[start] if start < k: re_start = start + 1 else: re_end = start - 1