Question: https://leetcode.com/problems/kth-largest-element-in-an-array/
Question Name: Kth Largest Element in an Array
This is exactly the quick-select.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | class Solution(object): def _quickSortHelper(self, nums, begin, end): """ :type nums: List[int] :type begin: int :type end: int :rtype: int (the index of nums[begin] after quick-select) """ next_smaller_pos = begin + 1 next_bigger_pos = end while next_smaller_pos <= next_bigger_pos: if nums[next_smaller_pos] <= nums[begin]: next_smaller_pos += 1 elif nums[begin] <= nums[next_bigger_pos]: next_bigger_pos -= 1 else: nums[next_smaller_pos] ^= nums[next_bigger_pos] nums[next_bigger_pos] ^= nums[next_smaller_pos] nums[next_smaller_pos] ^= nums[next_bigger_pos] next_smaller_pos += 1 nums[begin], nums[next_bigger_pos] = nums[next_bigger_pos], nums[begin] return next_bigger_pos def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ k = len(nums) - k begin, end = 0, len(nums) - 1 while True: position = self._quickSortHelper(nums, begin, end) if position == k: return nums[k] elif position < k: begin = position + 1 else: end = position - 1 # Should never be here. return 0 |