CODEWITHSUNDEEP
c++stl
TeemoMain
TeemoMain

Reputation: 105

How to find common numbers in two vectors of different sizes

I have two integer vectors of different sizes:

vector 1 = {1, 1, 3, 3, 3, 5, 5, 8, 8, 8}

vector 2 = {1, 3, 3, 5, 8}

I am trying to loop through both of these vectors and compare there values to see if they are similar then add them to a new vector.

Here is what I have tried:

vector<int> firstList{1, 1, 3, 3, 3, 5, 5, 8, 8, 8}
vector<int> secondList{1, 3, 3, 5, 8}
vector<int> finalList;

    for (std::vector<char>::iterator i = firstList.begin(); i != firstList.end(); ++i)
    {
        if (std::find(secondList.begin(), secondList.end(), *i) != secondList.end())
        {
            finalList.push_back(*i);
        }
    }

The output I expect in the finalList is: {1, 3, 3, 5, 8}

The actual output is: {1, 1, 3, 3, 3, 5, 5, 8, 8, 8} it returns 10 values when I only need 5.

Thanks for any help!

Upvotes: 0

Views: 674

Answers (3)

Akshay Bande
Akshay Bande

Reputation: 2587

The best way to do this in O(NlogN) is to sort both the vectors and loop both of them at the same time. 

sort(firstList.begin(),firstList.end());
sort(secondList.begin(),secondList.end());
int i = 0, j = 0;
while (i < firstList.size() && j < secondList.size())
{
    if (firstList[i] == secondList[j])
    {
        finalList.push_back(firstList[i]);
        i++;j++;
    }
    else if (firstList[i] < secondList[j])
    {
        i++;
    }
    else
    {
        j++;
    }
}

Upvotes: 0

Ranjeet
Ranjeet

Reputation: 382

You can use set. Initialize set with the largest vector.

using namespace std;

int main()
{
vector<int> firstList{1, 1, 3, 3, 3, 5, 5, 8, 8, 8};
vector<int> secondList{1, 3, 3, 5, 8};
vector<int> finalList;

set<int> firstSet{firstList.begin(),firstList.end()};
for(auto& i : secondList)
    if(*firstSet.find(i)) //find i in firstSet/firstList
       finalList.push_back(i);


for(auto& i : finalList)
   cout << i << " ";  //Output: 1 3 3 5 8 

}

Upvotes: 0

acegs
acegs

Reputation: 2809

make a copy of the smallest list and then remove found item on that list so on the next loop that found item will be excluded.

vector<int> firstList{1, 1, 3, 3, 3, 5, 5, 8, 8, 8}
vector<int> secondList{1, 3, 3, 5, 8}
vector<int> finalList;

vector<int> secondListCopy = secondList;

for (std::vector<int>::iterator i = firstList.begin(); i != firstList.end(); ++i)
{
    std::vector<int>::iterator i2 = std::find(secondListCopy.begin(), secondListCopy.end(), *i) ;
    if (i2 != secondListCopy.end())
    {
        finalList.push_back(*i);
        secondListCopy.erase(i2);

        if(secondListCopy.empty()) break; //just additional optimization.
    }
}

Upvotes: 1

Related Questions