0

如何使用向量 A 和向量 B 在 C++ 中找到集合之间的差异。我想出了联合和交集，但由于某种原因，无论我尝试什么都无法得到差异。任何帮助将不胜感激（顺便说一句，我需要手动完成，而不是使用内置方法。）

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <fstream>
#include <algorithm>

using namespace std;

void Difference();

int main()
{
    Difference();

    return 0;
}


void Difference()
{
    int temp = 0;
    vector<int> D{};
    vector<int> A{3, 4, 9, 12, 13, 15};

    vector<int> B{1, 3, 5, 7, 9};

    for(int i = 0; i < A.size(); i++)
    {
        for (int j = 0; j < B.size(); j++)
        {

            if (A[i] != B[j])
            {
                int temp = A[i];
                D.push_back(temp);
            }


                  //Used To Sort The Vector So There Is No Duplicates And Its In Order!
                  sort( D.begin(), D.end() );
                  D.erase( unique( D.begin(), D.end() ), D.end() );
        }

    }
    cout << "Difference: ";
    for(int z = 0; z < D.size(); z++)
    {
        cout << D[z] << " ";
    }
}
4

2 回答 2

2 
if (A[i] != B[j])
{
    int temp = A[i];
    D.push_back(temp);
}

您应该意识到，这将添加A[i]到向量D中的每个不等于的单个元素。因此，除非仅包含相同的元素，否则其中的所有内容都会使其跨越. 更详细地说，该操作将：BA[i]BAD{3, 4, 9} - {1, 3}

  • 添加3一次（因为它不等于1）；
  • 添加4两次（因为它等于既不1也不3）；和
  • 加9两次（因为它等于既不1也不3）。

{3, 4, 9}因此，在删除重复之后，尽管事实上3在两个向量中都存在，但您最终会得到。

您需要做的是检查是否有任何元素匹配，而不是像当前代码那样检查每个元素。这可以通过以下循环来完成：

// For each element in A.

for(size_t i = 0; i < A.size(); i++) {
    // Start by assuming not in B, then check every B.

    bool contains = false;
    for (size_t j = 0; j < B.size(); j++) {
        // If found in B, exit early and save that fact.

        if (A[i] == B[j]) {
            contains = true;
            break;
        }
    }

    // If it was not found in B, add it to D.

    if (! contains) {
        int temp = A[i];
        D.push_back(temp);
    }
}

这样，您也不必担心重复删除，除非原始向量中有重复项。如果是这种情况，您可能需要在原始算法（以及这个算法）中增加一些智能来处理（例如）{1, 2, 3, 3, 3}和{3}. 换句话说，应该是{1, 2}还是{1, 2, 3, 3}？

于 2020-09-09T00:26:09.950 回答
0 
#include <algorithm>
#include <iostream>
#include <vector>

void sort_and_unique(std::vector<int> &vec) {
  std::sort(vec.begin(), vec.end());
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

std::vector<int> difference(std::vector<int> a, std::vector<int> b) {
  sort_and_unique(a);
  sort_and_unique(b);
  std::vector<int> res;
  size_t left = 0, right = 0;
  while (left < a.size() && right < b.size()) {
    if (a[left] < b[right]) {
      res.emplace_back(a[left++]);
    } else if (a[left] == b[right]) {
      left++;
      right++;
    } else {
      right++;
    }
  }
  while (left < a.size()) {
    res.emplace_back(a[left++]);
  }
  return res;
}

int main() {
  std::vector<int> A{3, 4, 9, 12, 13, 15};
  std::vector<int> B{1, 3, 5, 7, 9};
  std::vector<int> res = difference(A, B);
  for (int x : res) {
    std::cout << x << ' ';
  }
  std::cout << std::endl;
  return 0;
}

这是一种O(nlogn)方法，它也删除重复元素。关键是要利用排序。使用两指针方法可以帮助实现它。

如果输入可靠（每个元素在其自己的向量中都是唯一的），则可以省略该vec.erase行。

于 2020-09-09T07:22:08.203 回答