Как я могу объединить три упорядоченных массива в один упорядоченный массив? В O (n)

Question

Мой код должен выбрать три массива и вернуть комбинацию из трех, массивы могут иметь разную длину. Код должен сделать комбинацию в O (n).

Пример: a [] = {1,2} b [] = {1,4,5} c [] = {2,4,5,6}

Мой результат должен быть: d [] = {1,1,2,2,4,4,5,5,6}

Answer 1

Один подход (и я уверен, что есть много других) будет:

Создать выходной массив на основе суммы длин входного массива:

int[] output = new int[a.length + b.length + c.length];

Создать индексуказатель для каждого из входных массивов:

int aIndex = 0;
int bIndex = 0;
int cIndex = 0;

Зациклите один раз для каждой позиции в выходном массиве и заполните его наименьшим значением для текущего индекса каждого входного массива (проверяя, что мы не использовалиэтот массив вверх):

for(int outputIndex = 0; outputIndex < output.length; outputIndex++) {
    if (aIndex < a.length
            && (bIndex >= b.length || a[aIndex] <= b[bIndex])
            && (cIndex >= c.length || a[aIndex] <= c[cIndex])) {
        output[outputIndex] = a[aIndex];
        aIndex++;
    } else if (bIndex < b.length
            && (aIndex >= a.length || b[bIndex] <= a[aIndex])
            && (cIndex >= c.length || b[bIndex] <= c[cIndex])) {
        output[outputIndex] = b[bIndex];
        bIndex++;
    } else {
        output[outputIndex] =  c[cIndex];
        cIndex++;
    }
}

Редактировать: Вот мой скомпилированный и протестированный код:

public class Join {

    public static void main(String[] args) {
        int[] a = {1, 2};
        int[] b = {1, 4, 5};
        int[] c = {2, 4, 5, 6};

        int[] output = new int[a.length + b.length + c.length];

        int aIndex = 0;
        int bIndex = 0;
        int cIndex = 0;

        for(int outputIndex = 0; outputIndex < output.length; outputIndex++) {
            if (aIndex < a.length
                    && (bIndex >= b.length || a[aIndex] <= b[bIndex])
                    && (cIndex >= c.length || a[aIndex] <= c[cIndex])) {
                output[outputIndex] = a[aIndex];
                aIndex++;
            } else if (bIndex < b.length
                    && (aIndex >= a.length || b[bIndex] <= a[aIndex])
                    && (cIndex >= c.length || b[bIndex] <= c[cIndex])) {
                output[outputIndex] = b[bIndex];
                bIndex++;
            } else {
                output[outputIndex] =  c[cIndex];
                cIndex++;
            }
        }
    }
}

Проверено в отладчике с точкой останова в конце метода.

Answer 2

[Отвечено перед добавлением ограничения O (n) при редактировании вопроса.]

Добавить все массивы в список и снова отсортировать. Примером может быть:

Integer[] a = {1, 2};
Integer[] b = {1, 4, 5};
Integer[] c = {2, 4, 5, 6};

List<Integer> lists = new ArrayList<>();
lists.addAll(Arrays.asList(a));
lists.addAll(Arrays.asList(b));
lists.addAll(Arrays.asList(c));

//print
lists
  .stream()
  .sorted()
  .forEach(System.out::println);