c++ 合并两个已排序数组

zpgglvta  于 2022-12-24  发布在  其他
关注(0)|答案(5)|浏览(211)

这是我的代码合并2排序数组:

#include<iostream>

using namespace std;

void merge(int arr1[], int n, int arr2[], int m, int arr3[]) {

    int i = 0, j = 0;
    int k = 0;
    while( i<n && j<m) {
        if(arr1[i] < arr2[j]){
            arr3[k++] = arr1[i++];
        }
        else{
            arr3[k++] = arr2[j++];
        }
    }
    
}

void print(int ans[], int n) {
    for(int i=0; i<n; i++) {
        cout<< ans[i] <<" ";
    }
    cout << endl;
}

int main() {

    int arr1[5] = {1,3,5,7,9};
    int arr2[3] = {2,4,6};

    int arr3[8] = {0};

    merge(arr1, 5, arr2, 3, arr3);

    print(arr3, 8);

    return 0;
}

我期望得到输出:
但我得到的输出是:
这是什么原因呢?

i1icjdpr

i1icjdpr1#

您需要处理到达较短列表末尾的情况,并且需要复制较长列表的其余部分。
这在下面的代码中由另外2个while循环处理。
另外,建议使用std::vector s而不是旧的c风格数组,这样你就不用手动跟踪数组大小了。

#include <iostream>
#include <vector>

void merge(std::vector<int> const & arr1, std::vector<int> const & arr2, std::vector<int> & arr3) {
    int i = 0, j = 0;
    int k = 0;
    arr3.resize(arr1.size() + arr2.size());
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            arr3[k++] = arr1[i++];
        }
        else {
            arr3[k++] = arr2[j++];
        }
    }
    // Copy the rest of arr1 (if needed):
    while (i < arr1.size()) {
        arr3[k++] = arr1[i++];
    }
    // Copy the rest of arr2 (if needed):
    while (j < arr2.size()) {
        arr3[k++] = arr2[j++];
    }
}

void print(std::vector<int> const & ans) {
    for (size_t i = 0; i < ans.size(); i++) {
        std::cout << ans[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr1 = { 1,3,5,7,9 };
    std::vector<int> arr2 = { 2,4,6 };
    std::vector<int> arr3;
    merge(arr1, arr2, arr3);
    print(arr3);
    return 0;
}

输出:
旁注:最好避免using namespace std-参见此处Why is "using namespace std;" considered bad practice?

1rhkuytd

1rhkuytd2#

这个循环,

while( i<n && j<m) {

到达最短数组的末尾时停止。在本例中,当m=3时。您需要继续从较大数组中复制其余元素

ny6fqffe

ny6fqffe3#

假设有一个“sentinel”值arr1[n] == arr2[m] == ∞,那么下面的代码就可以工作了,因为它将完全遍历两个数组,而不会越过(注意||)。

int i = 0, j = 0 k = 0;
while (i < n || j < m) {
    if (arr1[i] < arr2[j]) {
        arr3[k++]= arr1[i++];
    }
    else {
        arr3[k++]= arr2[j++];
    }
}

现在,您可以通过细化比较条件来模拟哨兵的存在:

arr1[i] < arr2[j]

变成

(i < n && j < m && arr1[i] < arr2[j]) || (i < n && j >= m)

可以写成

i < n && (j >= m || arr1[i] < arr2[j])

(检查案例n == im == j)。
请注意,将代码分成三个连续的循环,分别处理其中一个数组已被完全看到的情况,效率会更高。

f1tvaqid

f1tvaqid4#

你必须考虑边缘情况:-当一个链表结束时,你必须循环通过另一个链表并添加剩余的元素。
在你的例子中,arr 2有3个值,arr 1有5个值,所以当一个list元素结束时,你的while循环就结束了,在上面的例子中,arr 2也会结束,所以你必须在arr 3中添加arr 1元素
在while循环之后,必须添加以下代码

while (i < arr1.size()) arr3[k++] = arr1[i++];

    while (j < arr2.size()) arr3[k++] = arr2[j++];
57hvy0tb

57hvy0tb5#

你忘了一件事!
如果arr 1是1,2,3,arr 2是4,5,6,那么你只需要把arr1复制到arr3,你需要执行你写的循环;BUT则当您退出循环时,其中一个数组仍有项目需要复制,您只需复制其余元素即可。

void merge(int arr1[], int n, int arr2[], int m, int arr3[])
{
    int i = 0, j = 0;
    int k = 0;
    while (i < n && j < m)
    {
        if(arr1[i] < arr2[j]){
            arr3[k++] = arr1[i++];
        }
        else{
            arr3[k++] = arr2[j++];
        }
    }

    // Copy any remaining elements.
    // Note: Only one of these loops will do any work
    //       The other loop is a noop.
    while (i < n) {
        arr3[k++] = arr1[i++];
    }
    while (j < m) {
        arr3[k++] = arr2[j++];
    }    
}

我们可以简化一些事情:

if(arr1[i] < arr2[j]){
            arr3[k++] = arr1[i++];
        }
        else{
            arr3[k++] = arr2[j++];
        }

        // Could be written as:

        arr3[k++] = (arr1[i] < arr2[j]) ? arr1[i++] : arr2[j++];

第三运算符是一个快捷运算符,只计算一侧。
关于C++的其他注意事项

merge(arr1, 5, arr2, 3, arr3);

最好写成:

// Do not hard code the length of the array.
// Somebody in the future will come along and change the
// array and not look to where it is used and thus cause
// an error. Use `std::size()` to get the length of the array.
merge(arr1, std::size(arr1), arr2, std::size(arr2), arr3);

我也会改变操作来使用迭代器。这使得使用一些标准函数变得更容易。

template<typename I1, typename I2, typename I3>
void merge(I1 b1, I1 e1, I2 b2, I2, e2, I3 dst)
{
    while (b1 < e1 && b2 < e2)
    {
        *dst++ = (*b1 <= *b2) ? *b1++ : *b2++;
    }
    dst = std::copy(b1, e1, dst);
    dst = std::copy(b2, e2, dst);
}

然后您可以像这样使用它:

merge(std::begin(arr1), std::end(arr1),
      std::begin(arr2), std::end(arr2),
      std::begin(arr3));

相关问题