Home > OS >  Union of two sorted arrays in c
Union of two sorted arrays in c

Time:10-12

I am getting SEGMENTATION FAULT, as error can someone please help me find my mistake, I realise this isn't the most optimal code, any suggestion would be helpful, thanks

QUESTION: Given two arrays a[] and b[] of size n and m respectively. The task is to find union between these two arrays.

Union of the two arrays can be defined as the set containing distinct elements from both the arrays. If there are repetitions, then only one occurrence of element should be printed in the union.

Example 1:

Input: 5 3 1 2 3 4 5 1 2 3 Output: 5 Explanation: 1, 2, 3, 4 and 5 are the elements which comes in the union set of both arrays. So count is 5. Example 2:

Input: 6 2 85 25 1 32 54 6 85 2 Output: 7 Explanation: 85, 25, 1, 32, 54, 6, and 2 are the elements which comes in the union set of both arrays. So count is 7. Your Task: Complete doUnion funciton that takes a, n, b, m as parameters and returns the count of union elements of the two arrays. The printing is done by the driver code.

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

Expected Time Complexity : O((n m)log(n m)) Expected Auxilliary Space : O(n m)

MY ANSWERE:

    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;
        
    }```

CodePudding user response:

Here's my version, using vectors:

Edited: Changed the code to return the quantity of unique values.

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();
}

The algorithm is:

  1. Combine all both arrays into one vector.
  2. Sort the vector (this makes the next step easer).
  3. Remove all duplicate values so that only unique values are in the vector.
  4. Return the size of the vector, which is the number of unique values.

CodePudding user response:

And here is the C solution, keeping the C-Style array function prototype.

#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);
}

And if you want to have real low level stuff, then please see the ugly one below:

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

    int result[212];

    int* x = a;
    int* y = b;
    int* z = &result[0];

    while (x != (a   n) && y != (b   m)) {
        if (*x < *y)   x;
        else {
            if (!(*y < *x)) *z   = *x  ;
              y;
        }
    }
    return z - &result[0];
}
  • Related