LeetCode: 215. Kth Largest Element in an Array 数组中第k大元素
试题:
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 = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.
代码:
topk或者kth element问题通常可以使用快排和堆排解决。快排找出kth后再遍历一遍就能找到topk;堆排的堆顶就是kth element。
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> que = new PriorityQueue<Integer>(k);
for(int num : nums){
if(que.size()<k)
que.offer(num);
else if(que.peek()<num){
que.offer(num);
que.poll();
}
}
return que.peek();
}
}
//快速选择法
class Solution {
public int findKthLargest(int[] nums, int k) {
k = nums.length-k;
int low=0, high=nums.length-1;
while(low<high){ //不需要等于,当low=high-1时,已经排序好数组了。
int part = partition(nums, low, high);
if(part==k){
break;
}else if(part<k){
low = part+1;
}else{
high = part-1;
}
}
return nums[k];
}
private int partition(int[] nums, int low, int high){
int left=low, right=high+1;
while(true){
while(nums[++left]<nums[low] && left<high);
while(nums[--right]>nums[low] && right>low);
if(left>=right) break;
swap(nums,left,right);
}
swap(nums,low,right);
return right;
}
private void swap(int[] nums, int left, int right){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
k = len - k;
quickSort(nums, 0, len-1, k);
return nums[k];
}
public void quickSort(int[] nums, int start, int end, int target){
if(start < end){
int mid = partion(nums, start, end);
if(mid == target){
return;
}else if(mid > target){
quickSort(nums, start, mid-1, target);
}else if(mid < target){
quickSort(nums, mid+1, end, target);
}
}
}
public int partion(int[] nums, int start, int end){
int pivot = nums[start];
int left = start, right = end;
while(left < right){
while(left < right && nums[right] >= pivot) right--;
while(left < right && nums[left] <= pivot) left++;
if(left < right){
swap(nums, left, right);
}
}
swap(nums, start, right);
return right;
}
public void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
return;
}
}
还没有评论,来说两句吧...