Медианный алгоритм для 4 отсортированных массивов

Question

Мне нужно написать алгоритм для моего курса, чтобы найти среднее значение 4 отсортированных массивов разных размеров в O (n), и мне не разрешено создавать массив для хранения данных.как мне подойти к проблеме?Я думал о работе в цикле с 4 индексами, как будто я сортирую массивы в большой массив, а вместо этого просто запускаю без сохранения данных.цикл остановится на n / 2, и он должен дать мне среднее значение.написание кажется сложным и очень грязным (мне нужно проверить 4 массива, если я вышел за границы), есть ли лучший способ подойти к этому?

Answer 1

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

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

Некоторый код

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

Существует также место для дальнейшей оптимизации путем сортировки только до 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

Я думаю, что вы подошли к ключевой идее: медианное значение всех значений в четырех массивах - это просто медиана всех значений, поэтому, если мы пройдем половину всех значений, то все, что будет дальше, будет медианой.,Я бы предложил структурировать следующим образом:

int firstIndex = 0;
int secondIndex = 0;
int thirdIndex = 0;
int fourthIndex = 0;
double current;

for (int i = 0; i < n/2; i++) {
    // 1.) Find the value out of the four at firstIndex, secondIndex, ...
    //     which is smallest, and assign it to current
    // 2.) Increment whichever of the four indices belongs to that element
}
// whatever is in current at the end of the loop is the middle element

Вы, вероятно, хотите функцию findMin(int index1, int index2, int index3, int index4).Этот метод также может отвечать за проверки за пределами границ, поэтому основной цикл может просто полагаться на него, чтобы он указывал в правильном направлении, и не заботиться о том, что в нем нет элементов в любом данном массиве.

Имеет ли это смысл?Я попытался оставить достаточно двусмысленности, чтобы позволить вам справиться с большей частью реальной работы по реализации:)