使用O(1)空间在四个(单独)排序的数组中查找中位数 [英] Find median in four (individually) sorted arrays with O(1) space

问题描述

我分配了一个任务，以便在4个单独排序的数组中找到一个中位数.

中位数被定义为位于数组中间(在下标(N/2)处)的元素

要求:

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

我知道如何在O(1)空间和O(logn)时间的2个排序数组中找到一个中值，但是我找不到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个数组视为单个 unsorted 数组，分为4个部分.如果可以修改数组，则可以通过在它们之间交换值来对所有4个数组进行排序，就好像对1个数组进行排序(由于您知道对4个数组进行了排序，因此可以进行一些优化).对数组进行最多n/2个排序(其中n是4个数组的总长度)后，只需返回所有4个数组的中间值即可.

某些代码

下面的实现开始使多个数组像单个数组一样起作用.我已经实现了get，set和length方法，这是任何数组的基础.现在需要做的就是使用get(int)，set(int,int)和length()以及返回中位数median()的方法对类的数据进行排序(可能最多为n/2). /p>

也许有一种方法可以单次获取数组的中值，但是我想不到.快速排序和查找将以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;
    }

}

I have an assignment to find a median in 4 individually sorted arrays.

A median is defined as the element that is in the middle of the array (at index floor(N/2))

Requirements:

1. time complexity: linear to the size of the combined array
2. space complexity: O(1)

I know how to find a median in 2 sorted arrays with O(1) space and O(logn) time, but I cant find a good solution for 4 arrays that meets the requirement of O(1) space.

I have tried to adjust the algorithm for 3 arrays but it didn't work very well for me.

example for my assignment:

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

Thanks in advance

解决方案

Think of a single unsorted array

Consider thinking about the 4 arrays as a single unsorted array, broken into 4 parts. If you can modify the arrays, you can sort all 4 arrays as if 1 by swapping values between them (some optimizations can be made since you know the 4 arrays are sorted). Once you've sorted the arrays up to n/2 (where n is the aggregate length of the 4 arrays), just return the middle value of all 4.

Some Code

The implementation below begins to make multiple arrays function like a single one. I've implemented get, set, and length methods, the basis for any array. All that needs to happen now is for the class' data to be sorted (possibly up to n/2) using get(int), set(int,int), and length(), and a method which returns the median value median().

Perhaps there is a way to get the median value of an array in a single pass, I cannot think of it however. A quick sort and lookup will perform in O(nLogn) time complexity, only a single pass will reduce this to O(n) (linear to the size of the array).

There is also room for further optimization by sorting only up to n/2 within the median method, also when caching (i,j) pairs for each element when doing so.

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;
    }

}

这篇关于使用O(1)空间在四个(单独)排序的数组中查找中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！