215

""" 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明: 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。 """ # 堆实现 def findKthLargest(nums, k): def adjust_heap(idx, max_len): left = 2*idx + 1 right = 2*idx + 2 max_loc = idx if left < max_len and nums[max_loc] < nums[left]: max_loc = left if right < max_len and nums[max_loc] < nums[right]: max_loc = right if max_loc != idx: nums[idx], nums[max_loc] = nums[max_loc], nums[idx] adjust_heap(max_loc, max_len) # 建堆 n = len(nums) for i in range(n//2 -1, -1, -1): adjust_heap(i, n) res = None for i in range(1, k+1): res = nums[0] nums[0], nums[-i] = nums[-i], nums[0] adjust_heap(0, n-i) return res # 快排+迭代 import random class Solution: def partition(self, nums, l, r): k = random.randint(l, r) pivot = nums[k] nums[l], nums[k] = nums[k], nums[l] index = 1 for i in range(1+l, r+1): if nums[i] > pivot: index += 1 nums[i], nums[index] = nums[index], nums[i] nums[l], nums[index] = nums[index], nums[l] return index def findKthLargest(self, nums, k): l, r, k = 0, len(nums)-1, k-1 while l: p = self.partition(nums, l, r) if p == k: return nums[p] elif p>k: r = p-1 else: l = p+1