Найти медиану в четырех (индивидуально) отсортированных массивах с пробелом O (1)

Question

У меня есть задание найти медиану в 4 индивидуально отсортированных массивах.

Медиана определяется как элемент, который находится в середине массива (на уровне индекса (N / 2))

Требования:

1. сложность по времени: линейная по отношению к размеру объединенного массива
2. сложность пространства: O (1)

Я знаюкак найти медиану в 2 отсортированных массивах с O (1) пробелом и O (logn) временем, но я не могу найти хорошее решение для 4 массивов, которое соответствует требованию O (1) пробела.

IЯ пытался настроить алгоритм для 3 массивов, но он не очень хорошо работал для меня.

пример для моего задания:

A = {1 5 10 15 20}
B = {2 3 4 6 7}
C = {25 30 35 40 45}
D = {8 9 90 100 145}

median(A,B,C,D) = 10

Заранее спасибо

Answer 1

Подумайте об одном несортированном массиве

Рассмотрим 4 массива как один несортированный массив, разбитый на 4 части. Если вы можете изменить массивы, вы можете отсортировать все 4 массива, как если бы 1, поменяв местами значения между ними (можно провести некоторую оптимизацию, поскольку вы знаете, что 4 массива отсортированы). После того, как вы отсортировали массивы до n / 2 (где n - общая длина 4 массивов), просто верните среднее значение всех 4.

Какой-то код

Приведенная ниже реализация начинает делать несколько массивов функционирующими как один. Я реализовал get, set и length методы, основу для любого массива. Все, что должно произойти сейчас, - это сортировка данных класса (возможно, до n / 2) с использованием get(int), set(int,int) и length(), а также метод, который возвращает медианное значение median().

Возможно, есть способ получить медианное значение массива за один проход, однако я не могу об этом думать. Быстрая сортировка и поиск будут выполнять в O (nLogn) сложность времени, только один проход уменьшит это до O (n) (линейный к размеру массива).

Существует также место для дальнейшей оптимизации путем сортировки только до n / 2 в срединном методе, в том числе при кэшировании пар (i, j) для каждого элемента при этом.

int median( int[] a1, int[] a2, int[] a3, int[] a4 ) {
    MultiIntArray array = new MultiIntArray( a1, a2, a3, a4 );
    array.sort();
    return array.get( array.length() / 2 );
}

public class MultiIntArray {

    private int[][] data;

    public MultiIntArray( int[]... data ) {
        this.data = data;
    }

    public void sort() {
        // FOR YOU TO IMPLEMENT
    }

    public int length() {
        int length = 0;
        for ( int[] array : data ) {
            length += array.length;
        }
        return length;
    }

    public int get( int index ) {
        int i = 0;
        while ( index >= data[i].length ) {
            index -= data[i].length;
            i += 1;
        }
        return data[i][index];
    }

    public void set( int index, int value ) {
        int i = 0;
        while ( index >= data[i].length ) {
            index -= data[i].length;
            i += 1;
        }
        data[i][index] = value;
    }

}

Answer 2

С ограничением «сложность по времени равен размеру объединенных массивов», это тривиально, вы просто выбираете наименьший из первых элементов из четырех массивов n / 2 раза.Не требуется умный алгоритм.

Я уверен, что вы можете сделать это значительно быстрее.