0

我和我的朋友正在为合并功能而苦苦挣扎。它要求两个数组具有相同的大小，因此合并数组的数量是两倍。这是我们目前所拥有的：

void mergeTwoSortedArrays(const int a1[], const int a2[], int mergedArray[], int n) 
{
    int i = 0;
    int j = 0;
    int k = 0;

    while (i <= n && j <= n) 
    {
        if (a1[i] == a2[j]) 
        {
            mergedArray[k] = a1[i];
            mergedArray[k] = a2[j];
            i++;
            j++;
        }
        k++;
    }
}

但是它不起作用。有小费吗？

4

3 回答 3

4

这是用于合并排序还是什么？通常的方法是进行组合合并，就像您已经做过的那样，然后是副本。这是第一部分。你有点困惑。通读这个，你会发现它是有道理的：

while (i < n && j < n) {
    if (a1[i] <= a2[j]) {
        mergedArray[k++] = a1[i++];
    } else {
        mergedArray[k++] = a2[j++];
    }
}

然后你处理剩余的元素。显然，当只有一个数组到达末尾时，循环结束。所以现在你需要两个更简单的循环。只有一个会执行 - 不需要复杂的测试：

while (i < n) mergedArray[k++] = a1[i++];
while (j < n) mergedArray[k++] = a2[j++];

我把你的测试变成<了<=，因为数组是从零开始的。

于 2013-11-01T01:22:48.357 回答
0

这就是我想出的-

void mergeTwoSortedArrays(const int a1[], const int a2[], int mergedArray[], int n) {

    int i = 0;
    int j = 0;
    int k = 0;

    // Iterate and compare two input arrays until at least one of them reaches to boundary. 
    while (i < n && j < n) {
        if (a1[i] < a2[j]) {
            mergedArray[k++] = a1[i++];
        }
        else if (a1[i] > a2[j]) {
            mergedArray[k++] = a2[j++];
        }
        else if (a1[i] == a2[j]) {
            mergedArray[k++] = a1[i++];
            mergedArray[k++] = a2[j++];
        }
    }

    // Copy the remaining items from the other array, without comparison until, boundary.
    while (i < n) mergedArray[k++] = a1[i++];
    while (j < n) mergedArray[k++] = a2[j++];

}
于 2013-11-01T01:36:12.057 回答
0

我不知道您是要像交错那样合并它们还是只是连接两个不同的数组。如果它正在大步前进：

#include <iostream>

void mergeTwoArraysIntoOne(const int* lhs, const int* rhs, int* dst, size_t numElements) {
    const int* const endLhs = lhs + numElements;
    const int* const endRhs = rhs + numElements;
    for ( ; lhs < endLhs ; ) {
        while (rhs < endRhs && *rhs < *lhs)
            *(dst++) = *(rhs++);
        *(dst++) = *(lhs++);
    }
    while (rhs < endRhs)
        *(dst++) = *(rhs++);
}

void dumpArray(int* array, size_t elements) {
    for (size_t i = 0; i < elements; ++i)
        std::cout << array[i] << " ";
    std::cout << std::endl;
}

int main() {
    int array1[] = { 1, 2, 3 };
    int array2[] = { 10, 20, 30 };
    int array3[] = { 1, 11, 31 };

    int result[6];

    mergeTwoArraysIntoOne(array1, array2, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array2, array1, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array1, array3, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array3, array1, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array2, array3, result, 3);
    dumpArray(result, 6);

    mergeTwoArraysIntoOne(array3, array2, result, 3);
    dumpArray(result, 6);

    return 0;
}

现场演示：http: //ideone.com/7ODqWD

如果只是连接它们：

std::copy(&lhs[0], &lhs[numElements], &dst[0]);
std::copy(&rhs[0], &rhs[numElements], &dst[numElements]);
于 2013-11-01T06:32:10.190 回答