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.
For example,
Given
Given
[3,2,1,5,6,4]
and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
You may assume k is always valid, 1 ≤ k ≤ array's length.
Solution 1: Sort the array and return nums[k-1], it is O(nlogn) time and O(1) space.
Solution 2: QuickSort partition. O(n) best and O(n^2) worst. Can be shuffle to grantee the performance
public class Solution {
public int findKthLargest(int[] nums, int k) {
k--;
int lo=0, hi=nums.length-1;
while (lo<=hi) {
int[] p=partition(nums,lo,hi);
if (k>p[1]) lo=p[1]+1;
else if (k<p[0]) hi=p[0]-1;
else return nums[k];
}
return 0;
}
private int[] partition(int[] nums, int lo, int hi) {
int v=nums[lo];
int j=lo, i=lo+1, k=hi;
while (i<=k) {
if (nums[i]==v) i++;
else if (nums[i]<v) swap(nums,i,k--);
else swap(nums,i++,j++);
}
return new int[]{j,k};
}
private void swap(int[] nums, int i, int j) {
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
没有评论:
发表评论