K'th Smallest/Largest Element in Unsorted Array | Set 1 - GeeksforGeeks
When we can't change the original array:
http://python.dzone.com/articles/computer-algorithms-order
int leftSize;
int middleSize;
public PartitionResult(int left, int middle) {
this.leftSize = left;
this.middleSize = middle;
}
}
public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) throw new IllegalArgumentException();
int threshold = rank(array, k - 1);
int[] smallest = new int[k];
int count = 0;
for (int a : array) {
if (a < threshold) {
smallest[count] = a;
count++;
}
}
while (count < k) {
smallest[count] = threshold;
count++;
}
return smallest;
}
/* Find value with rank k in array. */
public static int rank(int[] array, int k) {
if (k >= array.length) {
throw new IllegalArgumentException();
}
return rank(array, k, 0, array.length - 1);
}
/* Find value with rank k in sub array between start and end. */
private static int rank(int[] array, int k, int start, int end) {
/* Partition array around an arbitrary pivot. */
int pivot = array[randomIntInRange(start, end)];
PartitionResult partition = partition(array, start, end, pivot);
int leftSize = partition.leftSize;
int middleSize = partition.middleSize;
if (k < leftSize) { // Rank k is on left half
return rank(array, k, start, start + leftSize - 1);
} else if (k < leftSize + middleSize) { // Rank k is in middle
return pivot; // middle is all pivot values
} else { // Rank k is on right
return rank(array, k - leftSize - middleSize, start + leftSize + middleSize, end);
}
}
/* Partition result into < pivot, equal to pivot -> bigger than pivot. */
private static PartitionResult partition(int[] array, int start, int end, int pivot) {
int left = start; /* Stays at (right) edge of left side. */
int right = end; /* Stays at (left) edge of right side. */
int middle = start; /* Stays at (right) edge of middle. */
while (middle <= right) {
if (array[middle] < pivot) {
/* Middle is smaller than the pivot. Left is either
* smaller or equal to the pivot. Either way, swap
* them. Then middle and left should move by one.
*/
swap(array, middle, left);
middle++;
left++;
} else if (array[middle] > pivot) {
/* Middle is bigger than the pivot. Right could have
* any value. Swap them, then we know that the new
* right is bigger than the pivot. Move right by one.
*/
swap(array, middle, right);
right--;
} else if (array[middle] == pivot) {
/* Middle is equal to the pivot. Move by one. */
middle++;
}
}
/* Return sizes of left and middle. */
return new PartitionResult(left - start, right - left + 1);
}
Approach 3: Selection Rank Algorithm (if elements are unique)
public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) {
throw new IllegalArgumentException();
}
int threshold = rank(array, k - 1);
int[] smallest = new int[k];
int count = 0;
for (int a : array) {
if (a <= threshold) {
smallest[count] = a;
count++;
}
}
return smallest;
}
/* Get item with rank. */
public static int rank(int[] array, int rank) {
return rank(array, 0, array.length - 1, rank);
}
/* Get element with rank between left and right indices. */
public static int rank(int[] array, int left, int right, int rank) {
int pivot = array[randomIntInRange(left, right)];
int leftEnd = partition(array, left, right, pivot); // returns end of left partition
int leftSize = leftEnd - left + 1;
if (rank == leftSize - 1) {
return max(array, left, leftEnd);
} else if (rank < leftSize) {
return rank(array, left, leftEnd, rank);
} else {
return rank(array, leftEnd + 1, right, rank - leftSize);
}
}
/* Partition array around pivot such that all elements <= pivot
* come before all elements > pivot. */
public static int partition(int[] array, int left, int right, int pivot) {
while (left <= right) {
if (array[left] > pivot) {
/* Left is bigger than pivot. Swap it to the right
* side, where we know it should be. */
swap(array, left, right);
right--;
} else if (array[right] <= pivot) {
/* Right is smaller than the pivot. Swap it to the
* left side, where we know it should be. */
swap(array, left, right);
left++;
} else {
/* Left and right are in correct places. Expand both
* sides. */
left++;
right--;
}
}
return left - 1;
}
/* Get random integer within range, inclusive. */
public static int randomIntInRange(int min, int max) {
Random rand = new Random();
return rand.nextInt(max + 1 - min) + min;
}
public static class MaxHeapComparator implements Comparator<Integer> {
public int compare(Integer x, Integer y) {
return y - x;
}
}
public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) {
throw new IllegalArgumentException();
}
PriorityQueue<Integer> heap = getKMaxHeap(array, k);
return heapToIntArray(heap);
}
/* Convert heap to int array. */
public static int[] heapToIntArray(PriorityQueue<Integer> heap) {
int[] array = new int[heap.size()];
while (!heap.isEmpty()) {
array[heap.size() - 1] = heap.poll();
}
return array;
}
/* Create max heap of smallest k elements. */
public static PriorityQueue<Integer> getKMaxHeap(int[] array, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k, new MaxHeapComparator());
for (int a : array) {
if (heap.size() < k) { // If space remaining
heap.add(a);
} else if (a < heap.peek()) { // If full and top is small
heap.poll(); // remove highest
heap.add(a); // insert new element
}
}
return heap;
}
public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) {
throw new IllegalArgumentException();
}
/* Sort array. */
Arrays.sort(array);
/* Copy first k elements. */
int[] smallest = new int[k];
for (int i = 0; i < k; i++) {
smallest[i] = array[i];
}
return smallest;
}
Read full article from K'th Smallest/Largest Element in Unsorted Array | Set 1 - GeeksforGeeks
Given an array and a number k where k is smaller than size of array, we need to find the k’th largest element in the given array. It is given that ll array elements are distinct.
Method 4 (QuickSelect)
In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.
In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.
int kthSmallest(int arr[], int l, int r, int k){ // If k is smaller than number of elements in array if (k > 0 && k <= r - l + 1) { // Partition the array around last element and get // position of pivot element in sorted array int pos = partition(arr, l, r); // If position is same as k if (pos-l == k-1) return arr[pos]; if (pos-l > k-1) // If position is more, recur for left subarray return kthSmallest(arr, l, pos-1, k); // Else recur for right subarray return kthSmallest(arr, pos+1, r, k-pos+l-1); } // If k is more than number of elements in array return INT_MAX;}
// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it// and greater elements to rightint partition(int arr[], int l, int r){ int x = arr[r], i = l; for (int j = l; j <= r - 1; j++) { if (arr[j] <= x) { swap(&arr[i], &arr[j]); i++; } } swap(&arr[i], &arr[r]); return i;}When we can't change the original array:
http://python.dzone.com/articles/computer-algorithms-order
Design an algorithm to find the smallest K numbers in an array
https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2017.%20Hard/Q17_14_Smallest_K
Approach 4: Selection Rank Algorithm (if elements are not unique)
The major change that needs to be made is to the partition function. When we partition the array around a pivot element, we now partition it into three chunks: less than pi vat, equal to pi vat, and greater than pivot.
public static class PartitionResult {int leftSize;
int middleSize;
public PartitionResult(int left, int middle) {
this.leftSize = left;
this.middleSize = middle;
}
}
public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) throw new IllegalArgumentException();
int threshold = rank(array, k - 1);
int[] smallest = new int[k];
int count = 0;
for (int a : array) {
if (a < threshold) {
smallest[count] = a;
count++;
}
}
while (count < k) {
smallest[count] = threshold;
count++;
}
return smallest;
}
/* Find value with rank k in array. */
public static int rank(int[] array, int k) {
if (k >= array.length) {
throw new IllegalArgumentException();
}
return rank(array, k, 0, array.length - 1);
}
/* Find value with rank k in sub array between start and end. */
private static int rank(int[] array, int k, int start, int end) {
/* Partition array around an arbitrary pivot. */
int pivot = array[randomIntInRange(start, end)];
PartitionResult partition = partition(array, start, end, pivot);
int leftSize = partition.leftSize;
int middleSize = partition.middleSize;
if (k < leftSize) { // Rank k is on left half
return rank(array, k, start, start + leftSize - 1);
} else if (k < leftSize + middleSize) { // Rank k is in middle
return pivot; // middle is all pivot values
} else { // Rank k is on right
return rank(array, k - leftSize - middleSize, start + leftSize + middleSize, end);
}
}
/* Partition result into < pivot, equal to pivot -> bigger than pivot. */
private static PartitionResult partition(int[] array, int start, int end, int pivot) {
int left = start; /* Stays at (right) edge of left side. */
int right = end; /* Stays at (left) edge of right side. */
int middle = start; /* Stays at (right) edge of middle. */
while (middle <= right) {
if (array[middle] < pivot) {
/* Middle is smaller than the pivot. Left is either
* smaller or equal to the pivot. Either way, swap
* them. Then middle and left should move by one.
*/
swap(array, middle, left);
middle++;
left++;
} else if (array[middle] > pivot) {
/* Middle is bigger than the pivot. Right could have
* any value. Swap them, then we know that the new
* right is bigger than the pivot. Move right by one.
*/
swap(array, middle, right);
right--;
} else if (array[middle] == pivot) {
/* Middle is equal to the pivot. Move by one. */
middle++;
}
}
/* Return sizes of left and middle. */
return new PartitionResult(left - start, right - left + 1);
}
Approach 3: Selection Rank Algorithm (if elements are unique)
public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) {
throw new IllegalArgumentException();
}
int threshold = rank(array, k - 1);
int[] smallest = new int[k];
int count = 0;
for (int a : array) {
if (a <= threshold) {
smallest[count] = a;
count++;
}
}
return smallest;
}
/* Get item with rank. */
public static int rank(int[] array, int rank) {
return rank(array, 0, array.length - 1, rank);
}
/* Get element with rank between left and right indices. */
public static int rank(int[] array, int left, int right, int rank) {
int pivot = array[randomIntInRange(left, right)];
int leftEnd = partition(array, left, right, pivot); // returns end of left partition
int leftSize = leftEnd - left + 1;
if (rank == leftSize - 1) {
return max(array, left, leftEnd);
} else if (rank < leftSize) {
return rank(array, left, leftEnd, rank);
} else {
return rank(array, leftEnd + 1, right, rank - leftSize);
}
}
/* Partition array around pivot such that all elements <= pivot
* come before all elements > pivot. */
public static int partition(int[] array, int left, int right, int pivot) {
while (left <= right) {
if (array[left] > pivot) {
/* Left is bigger than pivot. Swap it to the right
* side, where we know it should be. */
swap(array, left, right);
right--;
} else if (array[right] <= pivot) {
/* Right is smaller than the pivot. Swap it to the
* left side, where we know it should be. */
swap(array, left, right);
left++;
} else {
/* Left and right are in correct places. Expand both
* sides. */
left++;
right--;
}
}
return left - 1;
}
/* Get random integer within range, inclusive. */
public static int randomIntInRange(int min, int max) {
Random rand = new Random();
return rand.nextInt(max + 1 - min) + min;
}
public static class MaxHeapComparator implements Comparator<Integer> {
public int compare(Integer x, Integer y) {
return y - x;
}
}
public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) {
throw new IllegalArgumentException();
}
PriorityQueue<Integer> heap = getKMaxHeap(array, k);
return heapToIntArray(heap);
}
/* Convert heap to int array. */
public static int[] heapToIntArray(PriorityQueue<Integer> heap) {
int[] array = new int[heap.size()];
while (!heap.isEmpty()) {
array[heap.size() - 1] = heap.poll();
}
return array;
}
/* Create max heap of smallest k elements. */
public static PriorityQueue<Integer> getKMaxHeap(int[] array, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k, new MaxHeapComparator());
for (int a : array) {
if (heap.size() < k) { // If space remaining
heap.add(a);
} else if (a < heap.peek()) { // If full and top is small
heap.poll(); // remove highest
heap.add(a); // insert new element
}
}
return heap;
}
public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) {
throw new IllegalArgumentException();
}
/* Sort array. */
Arrays.sort(array);
/* Copy first k elements. */
int[] smallest = new int[k];
for (int i = 0; i < k; i++) {
smallest[i] = array[i];
}
return smallest;
}
Read full article from K'th Smallest/Largest Element in Unsorted Array | Set 1 - GeeksforGeeks
