C 中兩個排序陣列的并集

我收到 SEGMENTATION FAULT，因為錯誤有人可以幫助我找到我的錯誤，我意識到這不是最佳代碼，任何建議都會有所幫助，謝謝

題：

給定兩個陣列a[]和b[]大小分別為n和m。任務是找到這兩個陣列之間的聯合。

兩個陣列的并集可以定義為包含來自兩個陣列的不同元素的集合。如果有重復，則聯合中只應列印一次出現的元素。

示例 1：

輸入：

5 3
1 2 3 4 5
1 2 3

輸出：

5

解釋：

1、2、3、4 和 5 是兩個陣列的聯合集中的元素。所以計數是5。

示例 2：

輸入：

6 2 
85 25 1 32 54 6
85 2 

輸出：

7

解釋：85、25、1、32、54、6 和 2 是兩個陣列的聯合集中的元素。所以 count 是 7。 你的任務：完成 doUnion 函式，它以 a、n、b、m 作為引數并回傳兩個陣列的聯合元素的計數。列印由驅動程式代碼完成。

約束：

1 ≤ n, m ≤ 105
0 ≤ a[i], b[i] < 105

預期時間復雜度：O((n m)log(n m)) 預期輔助空間：O(n m)

我的答案：

//Function to return the count of number of elements in union of two arrays.
    int doUnion(int a[], int n, int b[], int m)  {
        //code here
        int mac;
            if(a[n-1]>=a[n-2] && a[n-2]>=a[n-3]){
                mac=a[n-1];
            }else{
                mac=a[0];
            }
            int mab;
            if(b[m-1]>=b[m-2] && b[m-2]>=b[m-3]){
                mab=b[m-1];
            }else{
                mab=b[0];
            }
            // cout<<mac<<" "<<mab<<endl;
        
        int ma = max(mac,mab);
        int ptr[ma 1]={0};
        
        for(int i = 0;i<n;i  )
        {
            ptr[a[i]]  ;
        }
        for(int i=0;i<m;i  )
        {
            ptr[b[i]]  ;
        }
        int u=0;
        
        for(int i=0;i<=ma;i  ){
            if(ptr[i]>0)
            {
                // cout<<i<<endl;
                u  ;
            }
        }
        return u;
        
    }

uj5u.com熱心網友回復：

這是我的版本，使用向量：

編輯： 更改了代碼以回傳唯一值的數量。

int doUnion(int a[], int n, int b[], int m)
{
     std::vector<int> the_union;
     for (int i = 0; i < n;   i)
     {
         the_union.push_back(a[i]);
     }
     for (int i = 0; i < m;   i)
     {
         the_union.push_back(b[i]);
     }
     std::sort(the_union.begin(), the_union.end());
     std::vector::iterator union_end_iter =  
         std::unique(the_union.begin(), the_union.end());

     // The `std::unique` does not remove the duplicate elements.
     the_union.erase(union_end_iter, the_union.end());
     // Return the number of unique elements:
     return the_union.size();
}

演算法是：

1. 將所有兩個陣列合并為一個向量。
2. 對向量進行排序（這使得下一步更容易）。
3. 洗掉所有重復值，以便向量中只有唯一值。
4. 回傳向量的大小，即唯一值的數量。

uj5u.com熱心網友回復：

這是 C 解決方案，保留 C 樣式陣列函式原型。

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

int doUnion(int a[], int n, int b[], int m) {
    std::vector<int> result{};
    std::set_intersection(a, a   n, b, b   m, std::back_inserter(result));
    return result.size();
}


int main() {
    int a[] = { 1,2,3,4,5,6,7,8,9 };    
    int b[] = {     3,    6,      10,11,12    };
    std::cout << doUnion(a, 9, b, 5);
}

如果你想要真正的低級東西，那么請看下面丑陋的：

int doUnion(int a[], int n, int b[], int m) {

    int* x = a;
    int* y = b;
    int counter = 0;

    while (x != (a   n) && y != (b   m)) {
        if (*x < *y)   x;
        else {
            if (!(*y < *x)){   x;   counter;}
              y;
        }
    }
    return counter;
}

標籤：C 算法 数据结构

上一篇：如何將2個陣列連接到第三個陣列中？

下一篇：來自外部類的片段中的SetText