如何将大小为 M 的数组合并到另一个大小为 2M 的数组

Question

我在在线代码挑战中遇到了这个问题。我需要合并两个排序数组，其中一个大小为 M，元素为 M，另一个数组为元素为 M，容量为 2M。我提供了以下解决方案：

class ArraysSorting {

/**
 * Function to move elements at the end of array
 * 
 * @param bigger array
 */
void moveToEnd(int bigger[]) {
    int i = 0, j = bigger.length - 1;
    for (i = bigger.length - 1; i >= 0; i--)
        if (bigger[i] != 0) {
            bigger[j] = bigger[i];
            j--;
        }
}

/**
 * Merges array smaller array of size M into bigger array of size 2M
 * @param bigger array
 * @param smaller array
 */
void merge(int bigger[], int smaller[]) {
    moveToEnd(bigger);
    int i = smaller.length;
    int j = 0;
    int k = 0;
    while (k < (bigger.length)) {
        if ((i < (bigger.length) && bigger[i] <= smaller[j]) || (j == smaller.length)) {
            bigger[k] = bigger[i];
            k++;
            i++;
        } else {
            bigger[k] = smaller[j];
            k++;
            j++;
        }
    }
  }
}

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

时间复杂度：O(2M)

Answer 1

您无法超越线性时间，因为您至少必须扫描所有 2M 个元素，所以这是您所能获得的最佳时间。

但实际上，您可以进一步优化它。不需要将 bigger 的元素移到最后；只需从右到左而不是从左到右写结果（当然，您需要反转比较，在任何步骤中您都希望 select 最大元素而不是最小元素).

另外，这样不好：

if ((i < (bigger.length) && bigger[i] <= smaller[j]) || (j == smaller.length)) {
    /* ... */
}

您应该在访问 smaller[j] 之前测试 j == smaller.length；原样的代码可能会访问 smaller 中的越界位置。改为这样做：

if ((j == smaller.length) || (i < (bigger.length) && bigger[i] <= smaller[j])) {
    /* ... */
}

总的来说，我确实认为你可以使代码更简单，在我看来，这里的代码更容易阅读，因为 if 条件更小且更容易理解（它也接近传统的方式您合并了两个数组并避免了将元素移到后面的额外 O(M) 工作):

void merge(int bigger[], size_t bigger_len, int smaller[], size_t smaller_len) {
    ssize_t smaller_i, bigger_i, idx;

    if (smaller_len == 0)
        return;

    smaller_i = smaller_len-1;

    if (bigger_len == 0)
        bigger_i = -1;
    else
        bigger_i = bigger_len-1;

    idx = bigger_len+smaller_len-1;

    while (smaller_i >= 0 && bigger_i >= 0) {
        if (bigger[bigger_i] > smaller[smaller_i]) {
            bigger[idx] = bigger[bigger_i];
            bigger_i--;
        }
        else {
            bigger[idx] = smaller[smaller_i];
            smaller_i--;
        }
        idx--;
    }

    while (smaller_i >= 0) {
        bigger[idx] = smaller[smaller_i];
        smaller_i--;
        idx--;
    }
}

很容易看出第一个循环运行只要可以比较不同数组中的两个元素（而不是让循环总是运行并使用复杂的 if 内部测试）。另请注意，由于输出正在写入 bigger，一旦第一个循环终止，我们只需要确保将剩余的 smaller 的其余部分（如果有的话）复制到 bigger.代码在 C 中，但在 Java 中几乎相同。 bigger_len和smaller_len是bigger和smaller中的元素个数；假定 bigger 有足够的 space 用于 bigger_len+smaller_len 元素。分配给 smaller_i 和 bigger_i 的初始 if 测试对于处理减 1 会溢出 size_t（无符号）范围的边缘情况是必要的；它们在 Java 中是不必要的，因为 Java 没有无符号类型（如果我错了请纠正我，我最近没做过 Java）。

时间复杂度保持 O(M).

如何将大小为 M 的数组合并到另一个大小为 2M 的数组

How to merge an array of size M into another array of size 2M

java

arrays

algorithm

big-o

mergesort