(referrence: GeeksforGeeks, Kth Largest Element in Array)
This is a common algorithm problem appearing in interviews.
There are four basic solutions.
Solution 1 -- Sort First
A Simple Solution is to sort the given array using a O(n log n) sorting algorithm like Merge Sort,Heap Sort, etc and return the element at index k-1 in the sorted array. Time Complexity of this solution is O(n log n).
Java Arrays.sort()
1 public class Solution{
2 public int findKthSmallest(int[] nums, int k) {
3 Arrays.sort(nums);
4 return nums[k];
5 }
6 }
Solution 2 -- Construct Min Heap
A simple optomization is to create a Min Heap of the given n elements and call extractMin() k times.
To build a heap, time complexity is O(n). So total time complexity is O(n + k log n).
Java Priority Queue
Using PriorityQueue(Collection c), we can construct a heap from array or other object in linear time.
By defaule, it will create a min-heap.
Example
1 public int generateHeap(int[] nums) {
2 int length = nums.length;
3 Integer[] newArray = new Integer[length];
4 for (int i = 0; i )
5 newArray[i] = (Integer)nums[i];
6 PriorityQueue pq = new PriorityQueue(Arrays.asList(newArray));
7 }
Comparator example
Comparator cmp = Colletions.reverseOrder();
Solution 3 -- Use Max Heap
1. Build a max-heap of size k. Put nums[0] to nums[k - 1] to heap.
2. For each element after nums[k - 1], compare it with root of heap.
a. If current >= root, move on.
b. If current < root, remove root, put current into heap.
3. Return root.
Time complexity is O((n - k) log k).
(Java: PriorityQueue)
(codes)
1 public class Solution {
2 public int findKthSmallest(int[] nums, int k) {
3 // Construct a max heap of size k
4 int length = nums.length;
5 PriorityQueue pq = new PriorityQueue(k, Collections.reverseOrder());
6 for (int i = 0; i )
7 pq.add(nums[i]);
8 for (int i = k; i ) {
9 int current = nums[i];
10 int root = pq.peek();
11 if (current < root) {
12 // Remove head
13 pq.poll();
14 // Add new node
15 pq.add(current);
16 }
17 }
18 return pq.peek();
19 }
20 }
Solution 4 -- Quick Select
public class Solution {
private void swap(int[] nums, int index1, int index2) {
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
// Pick last element as pivot
// Place all smaller elements before pivot
// Place all bigger elements after pivot
private int partition(int[] nums, int start, int end) {
int pivot = nums[end];
int currentSmaller = start - 1;
for (int i = start; i ) {
// If current element <= pivot, put it to right position
if (nums[i] <= pivot) {
currentSmaller++;
swap(nums, i, currentSmaller);
}
}
// Put pivot to right position
currentSmaller++;
swap(nums, end, currentSmaller);
return currentSmaller;
}
public int quickSelect(int[] nums, int start, int end, int k) {
int pos = partition(nums, start, end)
if (pos == k - 1)
return nums[pos];
if (pos )
return quickSelect(nums, pos + 1, end, k - (pos - start + 1));
else
return quickSelect(nums, start, pos - 1, k);
}
}
The worst case time complexity of this method is O(n2), but it works in O(n) on average.
Kth Smallest Element in Unsorted Array
京公网安备 11010802041100号