[C++]Find Different Elements Between Two Vectors in C++

There are two simple ways: Comparing Indexes and Hash Table.

1. Comparing Indexes

Here are two vectors.

string solution(vector<string> applicants, vector<string> successful)
{
  //do someting
}

Before comparing, the elements in both vetors need to be in order with std::sort().

  sort(applicants.begin(), applicants.end());
  sort(successful.begin(), successful.end());

Note: The time complexity of std::sort() is O(n log n).

It’s ready to compare the indexes of two vetors. If any differences are founded within for() statement, the index is returned.

for(int i = 0; i < successful.size(); ++i)
{
  if(applicants[i] != successful[i])
  {
    return applicants[i];
  }
}

2. unordered_map

Let’s create an unordered_map like this:

string solution(vector<string> applicants, vector<string> successful)
{
  unordered_map<string, int> solution_map;
}

Note: On an average the cost of search, insert and delete from Hash table is O(1).

Then, increment the values of each key in solution_map. On the same principle, decrement the values of each key which are in “successful”.

for(string name: applicants){
  solution_map[name]++;
  }
for(string name: successful){
  solution_map[name]--;
  }

Now we know the value bigger than 0 is the diffent element.

for(auto pair: solution_map){
  if (pair.second>0){
    return pair.first;
  }
}