Блог

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

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

Требования:

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

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

Я пытался настроить алгоритм для 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
  

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

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

Подумайте о том, чтобы рассматривать 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;
    }

}
  

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

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