-
Notifications
You must be signed in to change notification settings - Fork 13
/
FindKthLargest215.java
64 lines (60 loc) · 1.99 KB
/
FindKthLargest215.java
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
64
package Leetcode;
import java.util.Random;
public class FindKthLargest215 {
/**Method1: Partition of Quick Sort; Time: O(N), The Worst Time: O(N^2);; Space:O(logN) **/
Random random = new Random();
public int findKthLargest1(int[] nums, int k) {
return randomPartition(nums, 0, nums.length-1, nums.length - k);
}
private int randomPartition(int[] nums, int low, int high, int index) {
int randomK = low + random.nextInt(high - low +1);
swap(nums, randomK, high);
int partitionIndex = partition(nums, low, high);
if(partitionIndex == index) {
return nums[partitionIndex];
} else {
return partitionIndex < index ? randomPartition(nums, partitionIndex + 1, high, index) : randomPartition(nums, low, partitionIndex -1, index);
}
}
private int partition (int[] nums, int low, int high) {
int x = nums[high];
int i = low -1;
for (int m = low; m< high; m++) { if(nums[m] < x) { swap(nums, m, ++i); } }
swap(nums, i+1, high);
return i+1;
}
private void swap(int[] nums, int low, int high) {
int temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
/**Method2: Heap Sort; Time: O(NlogN);; Space:O(logN) **/
public int findKthLargest2(int[] nums, int k) {
int heapSize = nums.length;
int numsLen = nums.length;
buildMaxHeap(nums, heapSize);
for(int i = numsLen -1; i>=numsLen-k+1; i--) {
swap(nums, 0, i);
maxHeapify(nums, 0, --heapSize);
}
return nums[0];
}
private void buildMaxHeap (int[] nums, int heapSize) {
for(int i = heapSize/2; i >=0; i--) {
maxHeapify(nums, i, heapSize);
}
}
private void maxHeapify (int[] nums, int i ,int heapSize) {
int left = i * 2 +1, right = i*2+2, largest = i;
if(left < heapSize && nums[left] >nums[largest] ) {
largest = left;
}
if(right < heapSize && nums[right] > nums[largest]) {
largest = right;
}
if(i != largest) {
swap (nums, i, largest);
maxHeapify(nums, largest, heapSize);
}
}
}