Как уже говорили другие, K-й наименьший элемент - arr[k], после сортировки по возрастанию.
Это также известно как Алгоритм выбора , и самый известный алгоритм для случайного входного массива: Быстрый выбор , выполняется за O(n) время, которое тесно связано с Быстрая сортировка .
Я недавно написал реализацию, вы можете взглянуть.
код - в 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
(контрольный пример, через 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);
}
}
Советы:
- Он изменит входной массив, если не будет сделана копия.
- Поддерживается дублирование элементов.
- Код предназначен для понимания алгоритма, а не для производства.
Для производства, возможно, нужно выбрать стержень более случайно, я не уверен.
Для вашего исходного ввода
Поскольку вы получили 2 отсортированный массив , приведенный выше алгоритм не является обязательным.
Вы можете просто выполнить цикл по 2 массивам в одном цикле с одним указателем на каждый массив и добавить указатель с меньшим значением на 1 на каждом шаге, пока общий шаг не станет k.