五刷
Version #1 Quick Selection
Runtime: 1 ms, faster than 99.54% of Java online submissions for Kth Largest Element in an Array.
Memory Usage: 44.9 MB, less than 34.28% of Java online submissions for Kth Largest Element in an Array.
class Solution {
public int findKthLargest(int[] nums, int k) {
// select a num as pivot
// partition the array so that all elements to the pivot left are larger than or equals to it, all the elements to the pivot right are smaller than or equals to it
// if pivot is the kth element, return pivot
// else if pivot index is larger than k, start partitioning from the pivot's left
// else start partitioning from the pivot's right
if (nums == null || nums.length < k) {
throw new IllegalArgumentException();
}
k--;
int start = 0, end = nums.length - 1;
while (start < end) {
int n = partition(nums, start, end);
if (n == k) {
return nums[n];
} else if (n < k) {
start = n + 1;
} else {
end = n - 1;
}
}
return nums[k];
}
// partition the array between start and left
// return the index of the pivot number
// 0 1 2 3 4 5 6 7 8 middle = 4
// s e pivot = nums[4] = 2
// r l
// [5,6,3,5,3,4,2,1,2]
private int partition(int[] nums, int start, int end) {
int middle = start + (end - start) / 2;
int pivot = nums[middle];
swap(nums, middle, start);
int left = start + 1, right = end;
while (left <= right) {
while (left <= right && nums[left] > pivot) {
left++;
}
while (left <= right && nums[right] < pivot) {
right--;
}
if (left <= right) {
// swap
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
swap(nums, start, right);
return right;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
99.98 %
class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length < k) {
return 0;
}
// Randomly pick up a number, split the nums into 2 parts
// index
// <= num, num, >= num
// if index of num is larger than k, find k from [0,indexNum)
// if smaller than k, find k-(index+1) from (indexNum, len)
int start = 0;
int end = nums.length - 1;
Random rd = new Random();
int target = k;
//r sl e
// [6,2,3,1,2,4,5,5,3]
while (start < end) {
int curr = start + rd.nextInt(end - start + 1);
swap(nums, curr, end);
int left = start;
int right = end - 1;
while (left <= right) {
while (left <= right && nums[left] > nums[end]) {
left++;
}
while (left <= right && nums[right] < nums[end]) {
right--;
}
if (left <= right) {
swap(nums, left, right);
left++;
right--;
}
}
swap(nums, left, end);
if (left - start + 1 == target) { // target = 3
return nums[left];
} else if (left - start + 1 > target) {
end = left - 1;
} else {
target = target - (left - start + 1);
start = left + 1;
}
}
return nums[start];
}
private void swap(int[] nums, int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}
三刷
97.65 %
class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0 || k > nums.length) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start <= end) {
int pivotIndex = start + new Random().nextInt(end - start + 1);
int index = partition(nums, start, end, pivotIndex);
if (index == k - 1) {
return nums[index];
}
if (index > k - 1) {
end = index - 1;
} else {
start = index + 1;
}
}
return nums[start];
}
private int partition(int[] nums, int start, int end, int pivotIndex) {
// Partition the subarray [start, end] and return the index of pivot
int pivot = nums[pivotIndex];
swap(nums, pivotIndex, end);
int left = start;
int right = end - 1;
while (left <= right) {
while (left <= right && nums[left] > pivot) {
left++;
}
while (left <= right && nums[right] <= pivot) {
right--;
}
if (left <= right) {
swap(nums, left, right);
left++;
right--;
}
}
swap(nums, end, left);
return left;
}
private void swap(int[] nums, int i, int j) {
if (i == j) {
return;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
二刷
Random quick select
72.91 %
class Solution {
public int findKthLargest(int[] nums, int k) {
// QuickSelect
if (nums == null || nums.length == 0) throw new IllegalArgumentException();
int start = 0;
int end = nums.length - 1;
Random rd = new Random();
// [start, end]
while (start <= end) {
int random = start + rd.nextInt(end - start + 1);
int index = partition(nums, start, end, random);
if (index + 1 == k) return nums[index];
else if (index < k) {
start = index + 1;
} else {
end = index - 1;
}
}
return nums[end];
}
// given a pivot in subarray[start, end]-> find the index of pivot in the array
private int partition(int[] nums, int start, int end, int random) {
int pivot = nums[random];
nums[random] = nums[end];
nums[end] = pivot;
int left = start;
int right = end - 1;
while (left <= right) {
while (left <= right && nums[left] > pivot) left++;
while (left <= right && nums[right] < pivot) right--;
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
nums[end] = nums[left];
nums[left] = pivot;
return left;
}
}
这个总结很神
https://leetcode.com/problems/kth-largest-element-in-an-array/#/solutions
67.27 %
Version #1 MinHeap
- 最好不要命名为pq，用minHeap
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0 || nums.length < k) throw new IllegalArgumentException();
//min heap
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
for (int i = 0; i < nums.length; i++) {
if (pq.size() < k) {
pq.offer(nums[i]);
} else {
if (nums[i] > pq.peek()) {
pq.poll();
pq.offer(nums[i]);
}
}
}
return pq.peek();
}
}
Version #2 Quick Selection
二刷
94.62 %
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || k > nums.length) return -1;
//TODO
return quickSelect(nums, 0, nums.length - 1, k);
}
private int quickSelect(int[] nums, int start, int end, int k) {
if (start >= end) return nums[end];
int left = start;
int right = end;
int pivot = nums[(left + right) / 2];
while (left <= right) {
while (left <= right && nums[left] > pivot) left++;
while (left <= right && nums[right] < pivot) right--;
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
//find the kth->find the index = start + k - 1
if (start + k - 1 <= right) {
return quickSelect(nums, start, right, k);
} else if (start + k - 1 >= left) {
return quickSelect(nums, left, end, k - (left - start));
} else {
return nums[right + 1];
}
}
}
Another version
98.80 %
这里非常容易出错，如果内部不用while的话，需要保证所有的分支都是互斥的
这样保证每测试一次left <= right，两个指针都只移动一次
不然就会出错
while (left <= right) {
if (nums[left] > pivot) left++;
else if (nums[right] < pivot) right--;
else {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
一刷
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return -1;
}
return quickSelect(nums, 0, nums.length - 1, k);
}
private int quickSelect(int[] nums, int start, int end, int k) {
if (start >= end) {
return nums[start];
}
int left = start;
int right = end;
int pivot = nums[(left + right) / 2];
while (left <= right) {
while (left <= right && nums[left] > pivot) {
left++;
}
while (left <= right && nums[right] < pivot) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if (start + k - 1 <= right) {
return quickSelect(nums, start, right, k);
} else if (start + k - 1 >= left) {
return quickSelect(nums, left, end, k - (left - start));
} else return nums[right + 1];
}
}
No comments:
Post a Comment