Quickselect: O(N)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51// import java.util.*;
class Solution {
public int partition(int[] nums, int left, int right) {
int p = nums[left];
int i = left, j = right;
while (i < j) {
while (nums[j] >= p && i < j) {
j--;
}
while (nums[i] <= p && i < j) {
i++;
}
if (i < j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
nums[left] = nums[i];
nums[i] = p;
return i;
}
public int quickselect(int[] nums, int left, int right, int k_smallest) {
while (left < right) {
int p_idx = partition(nums, left, right);
if (p_idx < k_smallest) {
left = p_idx + 1;
} else if (p_idx > k_smallest) {
right = p_idx - 1;
} else {
break;
}
}
return nums[k_smallest];
}
public int findKthLargest(int[] nums, int k) {
// kth largest is (N - k)th smallest
return quickselect(nums, 0, nums.length - 1, nums.length - k);
}
}
/*
public class MyClass {
public static void main(String[] args) {
int[] nums = { 3, 2, 1, 5, 6, 4 };
System.out.println(new Solution().findKthLargest(nums, 1));
}
}*/
Java “Arrays.sort()” API (internal implementation: Dual-pivot Quicksort ): O(NlogN)1
2
3
4
5
6class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
MergeSort: O(NlogN)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
private void merge(int[] nums,int low,int mid,int high){
int[] tmp=new int[high-low+1];
int i=low,j=mid+1;
int k=0;
while(i<=mid&&j<=high){
if(nums[i]<nums[j]) tmp[k++]=nums[i++];
else tmp[k++]=nums[j++];
}
while(i<=mid) tmp[k++]=nums[i++];
while(j<=high) tmp[k++]=nums[j++];
for(int t=0;t<tmp.length;t++) nums[t+low]=tmp[t];
}
private void mergeSort(int[] nums,int low,int high){
int mid=low+(high-low)/2;
if(low<high){
mergeSort(nums,low,mid);
mergeSort(nums,mid+1,high);
merge(nums,low,mid,high);
}
}
public int findKthLargest(int[] nums, int k) {
mergeSort(nums,0,nums.length-1);
return nums[nums.length-k];
}
}