CODEWITHSUNDEEP
c++algorithmvectorintersection
user2757849
user2757849

Reputation: 247

Finding the Intersection between two Vectors

And I'm doing pretty good in fact I found the intersection and think I have the right code. Only problem is that it doesn't seem to print out the last value.

So if I have two sets:

9 12 7 8 1 19 11 2 14

15 10 8 2 5 16 14 7 19 0 11 3 13 18 9 17 1 12

My code will produce the following output: 

1
2
7
8
9
11
12
14

But the right intersection of the sets should be:

1
2
7
8
9
11
12
14
19

So, my code doesn't print out the last value and I can't find out why.

void findIntersection(vector<int> A, vector<int> B)
{
    vector<int> intersection;
    int n1 = A.size();
    int n2 = B.size();
    int i = 0, j =0;
    while(i <= n1 && j <= n2)
    {
        if(A[i] > B[j])
        {
            j++;
        }
        else if( B[j] > A[i])
        {
            i++;
        }
        else
        {
            intersection.push_back(A[i]);
            i++;
            j++;
        }
    }

    for(unsigned int i = 0; i <= intersection.size(); i++)
    {
        cout << intersection[i] << endl;
    }
}

void slowintersect(vector<vector<int> > v)
{
    vector<int> vec;
    vector<int> c;
    int store_0;

    int row = 0;
    for(size_t j =0; j < v.at(row).size(); j++)
    {
        store_0 = v[row][j];
        c.push_back(store_0);
    }

    for(size_t i = 0; i < v.size(); i++)
    {
        for(size_t k = 0; k < v.at(i).size(); k++)
        {
            vec.push_back(k);
        }
    }

    findIntersection(c, vec);
}

Upvotes: 2

Views: 10920

Answers (3)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

I'm assuming you do not want to use the C++ standard algorithm.

Couple of things.
1. Your algorithm shall work only if both vectors are initially sorted. Are they?
2. You shouldn't access vector[vector.size()] element as it is out of bounds.

My second point means: 

while(i <= n1 && j <= n2)

Change this to

while(i < n1 && j < n2)

And change the following

for(unsigned int i = 0; i <= intersection.size(); i++)

to

for(unsigned int i = 0; i < intersection.size(); i++)

Also, MOST IMPORTANT ERROR!!!!

for(size_t k = 0; k < v.at(i).size(); k++)
            {
                vec.push_back(k);

            }

Change it to:

for(size_t k = 0; k < v[i].size(); k++)
            {
                vec.push_back(v[i][k]);

            }

Upvotes: 3

4pie0
4pie0

Reputation: 29724

#include <algorithm>
#include <set>

set<int> intersect;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), // sorted!
                  std::inserter(intersect,intersect.begin()));

example

if you don't want std::algorithm, there are several errors in your code. i.e:

for(unsigned int i = 0; i <= intersection.size(); i++)
                           ^
                        should be <

here is an important error:

int i = 0, j =0;
while(i <= n1 && j <= n2)
{        ^          ^
         <          <
    if(A[i] > B[j])
    {
        j++;

you will skip all n-1 A elements if A[0] is greater than each B element, and end the loop

Upvotes: 7

Roland Illig
Roland Illig

Reputation: 41627

Your while co dition is broken. You must continue until both indexes are at the end. Currently you stop when one of the indexes has reached the end.

When you fix that, you also must ensure that you don't increase i beyond n1; same for j and n2.

While you are developing you should rather use vector.at(i) instead of vector[i] to enable safety checks.

Upvotes: 1

Related Questions