题目

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 [3,2,1,5,6,4] and k = 2, return 5.

Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.

朴素暴力法

public class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}


二分法

二分法代码

public class Solution {
public int findKthLargest(int[] nums, int k) {
return findKthSmallest(nums,0,nums.length-1,nums.length-k);
}
public int findKthSmallest(int[] nums, int low, int high, int k) {
int pivot = partition(nums,low,high);
if (pivot == k) {
return nums[pivot];
} else if (pivot < k) {
return findKthSmallest(nums,pivot+1,high,k);
} else {
return findKthSmallest(nums,low,pivot-1,k);
}
}
public int partition(int[] nums, int low, int high) {
if (low == high) { return low; }
int bound = low - 1;
int pivot = nums[high];
for (int i = low; i < high; i++) {
if (nums[i] <= pivot) {
bound++;
exchange(nums,bound,i);
}
}
bound++;
exchange(nums,bound,high);
return bound;
}
public void exchange(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}