Given an unsorted array, find the kth largest element.
Example
([3,2,1,5,6,4], 2) => 5
Brute Force
Sort the input array. Then return the n-k smallest element.
Arrays.sort(nums);
return nums[nums.length - k];
Priority Queue
We need to somehow structure this unstructured data. Maintain a min heap of size k. Poll as we go.
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
Time O(nlogk) Space O(k)
Quick Select
A true linear time algorithm doesn't exist for an unsorted array. But we can randomly pick a pivot and hope that it will structure some parts of the data. We can use the partition step from quick sort to help us to do that.
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return -1;
}
if (k <= 0 || k > nums.length) {
return -1;
}
return quickSelect(nums, nums.length - k + 1, 0, nums.length - 1);
}
// Quickly select the kth _smallest_ element
private int quickSelect(int[] arr, int k, int start, int end) {
// base case
if (start == end) {
return arr[start];
}
// divide
int pivotPos = partition(arr, start, end);
// conquer
if (k - 1 == pivotPos) {
return arr[pivotPos];
} else if (k - 1 < pivotPos) {
return quickSelect(arr, k, start, pivotPos - 1);
} else {
return quickSelect(arr, k, pivotPos + 1, end);
}
}
private int partition(int[] arr, int start, int end) {
int pivot = arr[start];
int i = start + 1, j = end;
while (i <= j) {
// swap after both pointers invalidate the condition
while (i <= j && arr[i] < pivot) i++;
while (i <= j && arr[j] >= pivot) j--;
if (i <= j) {
swap(arr, i, j);
i++;
j--;
}
}
// swap the pivot with the last element smaller than it
swap(arr, j, start);
return j;
}
Be mindful on the post condition after partition. j becomes the end the smaller section and i becomes the start of the larger section.
Time O(n) on average because the geometric sum proves T(n) = O(n) + T(n/2) = O(n).
k=length/2 if even k=length/2 + 1 if odd
public int median(int[] nums) {
int length = nums.length;
if (length % 2 == 1)
return findKthSmallest(nums, length / 2 + 1);
else
return findKthSmallest(nums, length / 2);
}
private int findKthSmallest(int[] arr, int k) {
return quickSelect(arr, k, 0, arr.length - 1);
}
Given an unordered list of building objects, find the best place a mailbox to minimize the total distance.
