如何将两个排序的数组合并为一个排序的数组？

Question

我在接受采访时被问及这是我提供的解决方案:

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length)
    {
        if (a[i] < b[j])
        {
            answer[k] = a[i];
            i++;
        }
        else
        {
            answer[k] = b[j];
            j++;
        }
        k++;
    }

    while (i < a.length)
    {
        answer[k] = a[i];
        i++;
        k++;
    }

    while (j < b.length)
    {
        answer[k] = b[j];
        j++;
        k++;
    }

    return answer;
}

有没有更有效的方法来做到这一点？

编辑:更正长度方法.

Answer 1

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)  
       answer[k++] = a[i] < b[j] ? a[i++] :  b[j++];

    while (i < a.length)  
        answer[k++] = a[i++];


    while (j < b.length)    
        answer[k++] = b[j++];

    return answer;
}

有点紧凑,但完全一样!

Answer 2

我很惊讶没有人提到这个更酷,更有效和紧凑的实现:

public static int[] merge(int[] a, int[] b) {
    int[] answer = new int[a.length + b.length];
    int i = a.length - 1, j = b.length - 1, k = answer.length;

    while (k > 0)
        answer[--k] =
                (j < 0 || (i >= 0 && a[i] >= b[j])) ? a[i--] : b[j--];
    return answer;
}

兴趣点

1. 请注意,它与其他任何O(n)算法的操作数相同或更少,但在单个while循环中只需单个语句!
2. 如果两个阵列的大小大致相同,则O(n)的常数相同.但是,如果数组实际上是不平衡的,那么版本System.arraycopy将获胜,因为在内部它可以使用单个x86汇编指令执行此操作.
3. 注意a[i] >= b[j]而不是a[i] > b[j].这保证了"稳定性",定义为当a和b的元素相等时,我们想要来自b之前的元素.

Answer 3

一个小的改进,但在主循环之后,你可以System.arraycopy用来复制任何一个输入数组的尾部,当你到另一个结束时.但是,这不会改变O(n)解决方案的性能特征.

Answer 4

可以进行的任何改进都是微优化,整体算法是正确的.

Answer 5

此解决方案也非常类似于其他帖子,除了它使用System.arrayCopy复制其余的数组元素.

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length +b.length];
    int i =0; int j = 0;int k = 0;
    while(i<a.length && j <b.length) {
        if(a[i]<b[j]) {
            result[k++] = a[i];
            i++;
        } else {
            result[k++] = b[j];
            j++;
        }
    }
    System.arraycopy(a, i, result, k, (a.length -i));
    System.arraycopy(b, j, result, k, (b.length -j));
    return result;
}

Answer 6

这是更新的功能.它删除重复,希望有人会发现这可用:

public static long[] merge2SortedAndRemoveDublicates(long[] a, long[] b) {
    long[] answer = new long[a.length + b.length];
    int i = 0, j = 0, k = 0;
    long tmp;
    while (i < a.length && j < b.length) {
        tmp = a[i] < b[j] ? a[i++] : b[j++];
        for ( ; i < a.length && a[i] == tmp; i++);
        for ( ; j < b.length && b[j] == tmp; j++);
        answer[k++] = tmp;
    }
    while (i < a.length) {
        tmp = a[i++];
        for ( ; i < a.length && a[i] == tmp; i++);
        answer[k++] = tmp;
    }
    while (j < b.length) {
        tmp = b[j++];
        for ( ; j < b.length && b[j] == tmp; j++);
        answer[k++] = tmp;
    }
    return Arrays.copyOf(answer, k);
}

Answer 7

它可以在4个语句中完成,如下所示

 int a[] = {10, 20, 30};
 int b[]= {9, 14, 11};
 int res[]=new int[a.legth+b.length]; 
 System.arraycopy(a,0, res, 0, a.length); 
 System.arraycopy(b,0,res,a.length, b.length);
 Array.sort(res)

Answer 8

GallopSearch 合并：O(log(n)*log(i))而不是 O(n)

我继续在评论中实施了灰胡子的建议。主要是因为我需要此代码的高效关键任务版本。

• 代码使用了一个 gallopSearch，它是 O(log(i))，其中 i 是相关索引存在的当前索引的距离。
• 在 gallop 搜索确定了正确的范围后，该代码使用 binarySearch。由于 gallop 将其限制在较小的范围内，因此生成的 binarySearch 也是 O(log(i))
• 疾驰和合并是向后执行的。这似乎不是关键任务，但它允许就地合并阵列。如果您的数组之一有足够的空间来存储结果值，您可以简单地将其用作合并数组和结果数组。在这种情况下，您必须在数组内指定有效范围。
• 在这种情况下它不需要内存分配（在关键操作中节省大量资金）。它只是确保它不会也不能覆盖任何未处理的值（只能向后完成）。事实上，您对输入和结果使用相同的数组。它不会受到任何不良影响。
• 我一直使用 Integer.compare() 因此可以将其用于其他目的。
• 有一些机会我可能会犯一点错误并且没有使用我以前证明过的信息。例如二进制搜索到两个值的范围内，其中一个值已经被检查过。可能还有更好的方法来说明主循环，如果将它们按顺序组合成两个操作，则不需要翻转 c 值。因为你知道你每次都会做一个然后另一个。有一些抛光的空间。

这应该是最有效的方法，时间复杂度为O(log(n)*log(i))而不是 O(n)。最坏情况时间复杂度为 O(n)。如果你的数组是块状的并且有很长的值串在一起，这将使任何其他方法相形见绌，否则它只会比它们更好。

它在合并数组的末尾有两个读取值，在结果数组中有写入值。在找出哪个最终值较小后，它会对该数组进行快速搜索。1, 2, 4, 8, 16, 32 等。当它找到另一个数组的读取值较大的范围时。它二进制搜索到该范围内（将范围减半，搜索正确的一半，重复直到单个值）。然后它数组将这些值复制到写入位置。请记住，副本必须移动，以便它不能覆盖任一读取数组中的相同值（这意味着写入数组和读取数组可以相同）。然后它对另一个数组执行相同的操作，该数组现在已知小于另一个数组的新读取值。

static public int gallopSearch(int current, int[] array, int v) {
    int d = 1;
    int seek = current - d;
    int prevIteration = seek;
    while (seek > 0) {
        if (Integer.compare(array[seek], v) <= 0) {
            break;
        }
        prevIteration = seek;
        d <<= 1;
        seek = current - d;
        if (seek < 0) {
            seek = 0;
        }
    }
    if (prevIteration != seek) {
        seek = binarySearch(array, seek, prevIteration, v);
        seek = seek >= 0 ? seek : ~seek;
    }
    return seek;
}

static public int binarySearch(int[] list, int fromIndex, int toIndex, int v) {
    int low = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = list[mid];
        int cmp = Integer.compare(midVal, v);
        if (cmp < 0) {
            low = mid + 1;
        } else if (cmp > 0) {
            high = mid - 1;
        } else {
            return mid;// key found
        }
    }
    return -(low + 1);// key not found.
}

static public int[] sortedArrayMerge(int[] a, int[] b) {
    return sortedArrayMerge(null, a, a.length, b, b.length);
}

static public int[] sortedArrayMerge(int[] results, int[] a, int aRead, int b[], int bRead) {
    int write = aRead + bRead, length, gallopPos;
    if ((results == null) || (results.length < write)) {
        results = new int[write];
    }
    if (aRead > 0 && bRead > 0) {
        int c = Integer.compare(a[aRead - 1], b[bRead - 1]);
        while (aRead > 0 && bRead > 0) {
            switch (c) {
                default:
                    gallopPos = gallopSearch(aRead, a, b[bRead-1]);
                    length = (aRead - gallopPos);
                    write -= length;
                    aRead = gallopPos;
                    System.arraycopy(a, gallopPos--, results, write, length);
                    c = -1;
                    break;
                case -1:
                    gallopPos = gallopSearch(bRead, b, a[aRead-1]);
                    length = (bRead - gallopPos);
                    write -= length;
                    bRead = gallopPos;
                    System.arraycopy(b, gallopPos--, results, write, length);
                    c = 1;
                    break;
            }
        }
    }
    if (bRead > 0) {
        if (b != results) {
            System.arraycopy(b, 0, results, 0, bRead);
        }
    } else if (aRead > 0) {
        if (a != results) {
            System.arraycopy(a, 0, results, 0, aRead);
        }
    }
    return results;
}

这应该是最有效的方法。

一些答案具有重复删除功能。这将需要 O(n) 算法，因为您必须实际比较每个项目。所以这是一个独立的，在事后应用。如果您需要查看所有条目，则无法一路浏览多个条目，但如果您有很多重复项，则可以浏览重复项。

static public int removeDuplicates(int[] list, int size) {
    int write = 1;
    for (int read = 1; read < size; read++) {
        if (list[read] == list[read - 1]) {
            continue;
        }
        list[write++] = list[read];
    }
    return write;
}

更新：以前的答案，不是可怕的代码，但明显不如上面的。

另一个不必要的超优化。它不仅为结束位调用 arraycopy，还为开头调用。通过二进制搜索将 O(log(n)) 中的任何介绍性非重叠处理到数据中。O(log(n) + n) 是 O(n) 并且在某些情况下效果会非常明显，尤其是在合并数组之间根本没有重叠的情况下。

private static int binarySearch(int[] array, int low, int high, int v) {
    high = high - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = array[mid];
        if (midVal > v)
            low = mid + 1;
        else if (midVal < v)
            high = mid - 1;
        else
            return mid; // key found
    }
    return low;//traditionally, -(low + 1);  // key not found.
}

private static int[] sortedArrayMerge(int a[], int b[]) {
    int result[] = new int[a.length + b.length];
    int k, i = 0, j = 0;
    if (a[0] > b[0]) {
        k = i = binarySearch(b, 0, b.length, a[0]);
        System.arraycopy(b, 0, result, 0, i);
    } else {
        k = j = binarySearch(a, 0, a.length, b[0]);
        System.arraycopy(a, 0, result, 0, j);
    }
    while (i < a.length && j < b.length) {
        result[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
    }
    if (j < b.length) {
        System.arraycopy(b, j, result, k, (b.length - j));
    } else {
        System.arraycopy(a, i, result, k, (a.length - i));
    }
    return result;
}