-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_215.java
More file actions
63 lines (56 loc) · 1.8 KB
/
Copy pathP_215.java
File metadata and controls
63 lines (56 loc) · 1.8 KB
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
52
53
54
55
56
57
58
59
60
61
62
63
package leetcode.medium;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;
public class P_215 {
// Sort - O(n log n) // O(1)
public int findKthLargestSort(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
// Priority Queue - O(n log k) // O(k)
public int findKthLargestPQ(int[] nums, int k) {
final PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.add(num);
if (pq.size() > k) {
pq.remove();
}
}
return pq.element();
}
// Randomized Quick Select - average O(n) // O(1)
public int findKthLargest(int[] nums, int k) {
int low = 0, high = nums.length - 1;
final Random random = new Random();
while (low <= high) {
final int pivotIdx = random.nextInt(high - low + 1) + low;
final int newPivotIdx = partition(nums, low, high, pivotIdx);
if (newPivotIdx == k - 1) {
return nums[newPivotIdx];
} else if (newPivotIdx > k - 1) {
high = newPivotIdx - 1;
} else {
low = newPivotIdx + 1;
}
}
return low;
}
private static int partition(int[] nums, int low, int high, int pivotIdx) {
final int pivotVal = nums[pivotIdx];
int newPivotIdx = low;
swap(nums, pivotIdx, high);
for (int i = low; i < high; i++) {
if (nums[i] > pivotVal) {
swap(nums, i, newPivotIdx++);
}
}
swap(nums, high, newPivotIdx);
return newPivotIdx;
}
private static void swap(int[] nums, int i, int j) {
final int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}