K-й наименьший элемент и K-й элемент?

Как вы уже указали, объединение двух массивов будет тем, что вы ищете. Итак, вот пример:

S = [0,4,5,7]
T = [1,2,8,9]
then A = S v T = [0,1,2,4,5,7,8,9]

Теперь, когда вы просматриваете этот массив, вы обнаружите, что k-й элемент имеет индекс k-1. Это потому, что мы склонны начинать отсчет с один вверх. Поэтому мы говорим первый элемент и имеем в виду элемент с индексом 0.

Вслед за этим, это также ответ на ваш другой вопрос. Поскольку у вас есть два массива, k-е наименьшее число будет в A[k-1], но ваш учитель имел в виду, что в любом из массивов, поэтому S и T они могут не быть в индексе k-1. В приведенном выше примере 5-е наименьшее число — это 5 по индексу 4 в A, но это третий элемент в S или S[2].

The output is not necessarily at index k of either list? What does it means?

Это означает, что вы должны решить проблему, не создавая C, она же AUB.

Вместо этого вы должны перебирать оба массива параллельно, пока не найдете k-й наименьший элемент.

Псевдологика:

Ai = 0, Bi = 0
Loop K-1 times:
    if A[Ai] < B[Bi] then Ai++ else Bi++
kth smallest = min(A[Ai], B[Bi])

Пример

A = [10, 20, 40, 60], B =[15, 35, 50, 70, 100], K = 4

Ai = 0, Bi = 0: A[0] < B[0] so Ai++
Ai = 1, Bi = 0: A[1] > B[0] so Bi++
Ai = 1, Bi = 1: A[1] < B[1] so Ai++
Ai = 2, Bi = 1: min(A[2], B[1]) = 35

4-е наименьшее значение — 35, находится в B[1].

Как видите, вывод находится не в индексе 3 (=4-1) ни в одном из списков.

Kth smallest Element and Kth Element?

А поскольку вы никогда не создаете комбинированный список, а вместо этого работаете сразу с двумя разными списками, K-го элемента нет, поэтому вопрос, поставленный в заголовке, не имеет смысла.

Объединение двух массивов — это просто массив, содержащий все элементы обоих массивов.

Например A[1,20,40,70] and B[10,50,60,80] Объединение двух вышеуказанных массивов может быть C[1,20,40,70,10,50,60,80]

Теперь предположим, что диапазон k начинается с 1 (включительно), предположим, что k = 3 , теперь k-й элемент равен 40, а k-й наименьший элемент равен 20.

Способ сделать это эффективно зависит от того, как вы подходите к этому. Один (не слишком эффективный) подход может заключаться в простом использовании k вложенных итераций и поиске k-го наименьшего элемента из несортированного массива объединений.

Другим подходом может быть сортировка массива после объединения, другой способ - просто объединить два массива, чтобы результирующее объединение было отсортировано (сортировка слиянием: процедура слияния). В таком случае результирующий массив будет иметь k-й наименьший элемент, такой же, как k-й элемент.

Как говорили другие, 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.