Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.找出一个非排序数组中第k大的元素。
解法1：排序法。使用常规排序方法后找到数组中对应下标的值。
解法2：将数组内容存入一升序优先队列中，进行k-1次pop操作，那么队尾的元素就是第k大的数字。
解法3：最大堆MaxHeap。使用数组内容构建一个最大堆，通过每次pop出堆顶后继续维护堆的结构，直到满足一定的次数（最大堆k-1次，最小堆size-k次），堆顶的元素就是第k大的数字，实现的效果与优先队列相同。
解法4：Quick Select, 利用快排的partition函数思想，选定一个数组内的值作为pivot，将小于pivot的数字放到pivot右边，大于等于pivot的数字放到pivot左边。接着判断两边数字的数量，如果左边的数量小于k个，说明第k大的数字存在于pivot及pivot右边的区域之内，对右半区执行partition函数；如果右边的数量小于k个，说明第k大的数字在pivot和pivot左边的区域之内，对左半区执行partition函数。直到左半区刚好有k-1个数，那么第k大的数就已经找到了。
Java: Sort, T: O(nlogn) S: O(1)
public class Solution { public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; }} Java: MaxHeap, T: O(nlogk) S: O(k)
public class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue p = new PriorityQueue (); for(int i = 0 ; i < nums.length; i++){ p.add(nums[i]); if(p.size()>k) p.poll(); } return p.poll(); }} Java: Quick select, T: Avg O(n) Worst O(n^2), S: O(1)
public class Solution { public int findKthLargest(int[] nums, int k) { return quickSelect(nums, k - 1, 0, nums.length - 1); } private int quickSelect(int[] arr, int k, int left, int right){ int pivot = arr[(left + right) / 2]; int orgL = left, orgR = right; while(left <= right){ // 从右向左找到第一个小于枢纽值的数 while(arr[left] > pivot){ left ++; } // 从左向右找到第一个大于枢纽值的数 while(arr[right] < pivot){ right --; } // 将两个数互换 if(left <= right){ swap(arr, left, right); left ++; right --; } } // 最后退出的情况应该是右指针在左指针左边一格 // 这时如果右指针还大于等于k，说明kth在左半边 if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right); // 这时如果左指针还小于等于k，说明kth在右半边 if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR); return arr[k]; } private void swap(int[] arr, int idx1, int idx2){ int tmp = arr[idx1] + arr[idx2]; arr[idx1] = tmp - arr[idx1]; arr[idx2] = tmp - arr[idx2]; }} Python: Sort
class Solution: # @param {integer[]} nums # @param {integer} k # @return {integer} def findKthLargest(self, nums, k): return sorted(nums, reverse=True)[k - 1] Python: Max Heap
from heapq import *class Solution(object): def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ if not nums: return -1 h = [] for i in xrange(len(nums)): if len(h) < k: heappush(h, nums[i]) else: if h[0] < nums[i]: heappop(h) heappush(h, nums[i]) return h[0]
Python: Quick select
import randomclass Solution: def findKthLargest(self, nums, k): pivot = random.choice(nums) nums1, nums2 = [], [] for num in nums: if num > pivot: nums1.append(num) elif num < pivot: nums2.append(num) if k <= len(nums1): return self.findKthLargest(nums1, k) if k > len(nums) - len(nums2): return self.findKthLargest(nums2, k - (len(nums) - len(nums2))) return pivot
Python: Quick select
class Solution: # @param {integer[]} nums # @param {integer} k # @return {integer} def findKthLargest(self, nums, k): left, right = 0, len(nums) - 1 while left <= right: pivot_idx = randint(left, right) new_pivot_idx = self.PartitionAroundPivot(left, right, pivot_idx, nums) if new_pivot_idx == k - 1: return nums[new_pivot_idx] elif new_pivot_idx > k - 1: right = new_pivot_idx - 1 else: # new_pivot_idx < k - 1. left = new_pivot_idx + 1 def PartitionAroundPivot(self, left, right, pivot_idx, nums): pivot_value = nums[pivot_idx] new_pivot_idx = left nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx] for i in xrange(left, right): if nums[i] > pivot_value: nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i] new_pivot_idx += 1 nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right] return new_pivot_idx C++: Sort
class Solution {public: int findKthLargest(vector & nums, int k) { sort(nums.begin(), nums.end()); return nums[nums.size() - k]; }}; C++: Priority queque
class Solution { public: int findKthLargest(vector & nums, int k) { /** priority_queue