As others said, K-th smallest element is arr[k], after sorting ascendingly.
This is also known as Selection algorithm, and the best known algorithm for random input array is Quick select, runs in O(n) time, which is closely related to Quick Sort.
I happen to wrote an implementation recently, you may take a look.
Code - in Java
QuickSelect.java
/**
* Find k-th smallest element from an array, via quick select.
*
* @author eric
* @date 3/24/19 3:49 PM
*/
public class QuickSelect {
/**
* Find k-th smallest element, of given array.
*
* @param arr input array, will be modified (sorted partially),
* @param k k-th, start from 0,
* @return index of k-th, in the array,
*/
public static int findKth(int[] arr, int k) {
if (k < 0 || k >= arr.length)
throw new IllegalArgumentException("array length = " + arr.length + ", thus k should < " + arr.length + ", but get: " + k);
return findKth(arr, k, 0, arr.length - 1);
}
/**
* Find k-th smallest element, of given sub array.
*
* @param arr input array, will be modified (sorted partially),
* @param k k-th, start from 0,
* @param start inclusive
* @param end inclusive
* @return index of k-th, in the array,
*/
public static int findKth(int[] arr, int k, int start, int end) {
if (start == end && start == k) return k; // base case,
int pvt = end; // index of pivot, initially taken from last element of sub array,
// check each element in sub array,
for (int i = start; i <= end; i++) {
if (i < pvt && arr[i] > arr[pvt]) { // on left of pivot, and it's larger,
if (pvt - i == 1) { // neighbor, just switch,
int tmp = arr[i];
arr[i] = arr[pvt];
arr[pvt] = tmp;
} else { // not neighbor,
// swap 3 positions,
int tmp = arr[i];
arr[i] = arr[pvt - 1];
arr[pvt - 1] = arr[pvt];
arr[pvt] = tmp;
pvt -= 1; // adjust pvt,
i--; // restart from i,
}
} else if (i > pvt && arr[i] < arr[pvt]) { // on right of pivot, and it's smaller,
if (i - pvt == 1) { // neighbor, just switch,
int tmp = arr[i];
arr[i] = arr[pvt];
arr[pvt] = tmp;
} else {
// swap 3 positions,
int tmp = arr[i];
arr[i] = arr[pvt + 1];
arr[pvt + 1] = arr[pvt];
arr[pvt] = tmp;
pvt += 1; // adjust pvt,
// continue from i+1;
}
}
}
int leftSize = pvt - start; // element count on left side of pivot, in sub array,
if (leftSize == k) { // pivot itself is k-th,
return pvt;
} else if (leftSize > k) {
return findKth(arr, k, start, pvt - 1); // find on left part,
} else {
return findKth(arr, k - leftSize - 1, pvt + 1, end); // find on right part,
}
}
}
QuickSelectTest.java
(Test case, via TestNG)
import eric.algorithm.dynamic.ShufflePerfectly;
import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
import java.util.Arrays;
/**
* QuickSelect test.
*
* @author eric
* @date 3/24/19 3:50 PM
*/
public class QuickSelectTest {
private int size = 20; // array size, should be even,
private int[] arr; // array with unique elements,
private int[] arrDup; // array with duplicated elements,
@BeforeMethod
private void setUp() {
// init - arr,
arr = new int[size];
for (int i = 0; i < size; i++) arr[i] = i;
ShufflePerfectly.shuffle(arr); // shuffle,
// System.out.printf("[initial] arr = %s\n", Arrays.toString(arr));
// init - arrDup,
arrDup = new int[size];
int halfIdx = size / 2;
for (int i = 0; i < halfIdx; i++) {
arrDup[i] = i;
arrDup[i + halfIdx] = i;
}
ShufflePerfectly.shuffle(arrDup); // shuffle,
// System.out.printf("[initial] arrDup = %s\n", Arrays.toString(arrDup));
}
@Test
public void test() {
System.out.printf("\n[initial]: arr = %s\n", Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
// setUp(); // re-random array,
int idx = QuickSelect.findKth(arr, i);
Assert.assertEquals(idx, i); // check index,
Assert.assertEquals(arr[idx], i); // check value,
System.out.printf("[after %d-th]: arr = %s\n", i, Arrays.toString(arr));
}
}
@Test
public void test_dup() {
System.out.printf("\n[initial]: arrDup = %s\n", Arrays.toString(arrDup));
for (int i = 0; i < arr.length; i++) {
// setUp(); // re-random array,
int idx = QuickSelect.findKth(arrDup, i);
Assert.assertEquals(idx, i); // check index,
Assert.assertEquals(arrDup[idx], i / 2); // check value,
System.out.printf("[after %d-th]: arrDup = %s\n", i, Arrays.toString(arrDup));
}
}
@Test(expectedExceptions = IllegalArgumentException.class)
public void test_invalid_outOfRange() {
QuickSelect.findKth(arr, arr.length);
}
@Test(expectedExceptions = IllegalArgumentException.class)
public void test_invalid_negative() {
QuickSelect.findKth(arr, -1);
}
}
Tips:
- It will modify input array, unless a copy is made.
- It support duplicated elements.
- The code is for understanding the algorithm, not for production.
For production, maybe need to choose the pivot more randomly, I am not sure.
For your original input
Since you got 2 sorted array, the algorithm above is not necessary.
You could simply loop through the 2 array in a single loop, with one pointer for each array, and add the pointer with smaller value by 1 on each step, till the total step is k.
[42, 0, 5]? – Code-Apprentice