arrays - 在具有 O(1) 空间的四个(单独)排序数组中查找中位数

Question

我有一个作业要在 4 个单独排序的数组中找到中位数。

中位数定义为位于数组中间的元素(在索引 floor(N/2))

要求:

1. 时间复杂度:与组合数组的大小成线性
2. 空间复杂度:O(1)

我知道如何在具有 O(1) 空间和 O(logn) 时间的 2 个排序数组中找到中位数，但我找不到满足 O(1) 空间要求的 4 个数组的好的解决方案。

我曾尝试调整 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 方法，它们是任何数组的基础。现在需要做的就是使用 get(int)、set(int,int) 对类的数据进行排序(可能最多 n/2)，和 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;
    }

}