我正在尝试找到 2 个排序数组(有重复)的并集,但我觉得我没有想出最优雅的代码(顺便说一句,我已经工作了,我只是觉得我可以减少一些代码行).假设我有 2 个向量 a = {1,3,3,4,4,4,5,7} 和 b = {1,3,3,3,5,5,5,6,8,9} 和我想将它们的并集存储在一个名为 unionVector 的向量中(它将是 1,3,4,5,6,7,8,9)
这是我的代码:
#include <iostream>
#include <vector>
using namespace std;
// Prints the contents of a vector
void printVector(vector<int> a){
if(a.size() == 0)
return;
else{
for(int i = 0; i < a.size(); i++)
cout << a[i] << '\t';
}
cout << endl;
}
// Print the union of 2 sorted arrays with duplicates
void printUnion(int *a, int aSize, int *b, int bSize){
if(aSize == 0 && bSize == 0)
return;
else{
vector<int> unionVector;
int i = 0;
int j = 0;
int last = 0;
// insert the smaller of first element regardless
if(a[i] < b[j]){
unionVector.push_back(a[i]);
i++;
}
else if (b[j] < a[i]){
unionVector.push_back(b[j]);
j++;
}
else{// both are equal numbers
unionVector.push_back(a[i]);
i++;
j++;
}
// now traverse both the loops one increment at a time
while(i < aSize && j < bSize){
last = unionVector[unionVector.size() - 1];
if(a[i] < b[j]){
if(last != a[i])
unionVector.push_back(a[i]);
i++; // increment i in either case
}
else if(b[j] < a[i]){
if(last != b[j])
unionVector.push_back(b[j]);
j++;
}
else{
// both of the numbers are equal
if(last != a[i])
unionVector.push_back(a[i]);
i++;
j++;
}
}
// lets say if 1 array wasn't complete
while(i < aSize){
last = unionVector[unionVector.size() - 1];
if(last != a[i])
unionVector.push_back(a[i]);
i++;
}
while(j < bSize){
last = unionVector[unionVector.size() - 1];
if(last != b[i])
unionVector.push_back(b[j]);
j++;
}
printVector(unionVector);
}
}
int main(){
int a[] = {1,3,3,4,4,4,5,7};
int b[] = {1,3,3,3,5,5,5,6,7,7,8,9};
printUnion(a,8,b,12);
return 0;
}
事情是因为可能有重复项,我检查要插入的元素和最后一个插入到 unionVector 中的元素。我需要确保当 unionVector 为空时我不会尝试获取“最后一个”元素,这就是为什么我无论如何都要在 unionVector 中插入 1 个元素。如果有人可以建议一种无需先插入 1 个元素即可进行检查的方法,我将不胜感激(我正在考虑使用一个标志变量来检查 unionVector 是否为空,但我觉得这太乱了)
编辑 1:
- 这不是作业问题。这是我在面试中练习的内容
编辑 2:
- 我也不能使用任何内置函数
编辑 3:
- 如果这是 C++ 职位,有些人会感到困惑。您可以使用任何您想要的语言
最佳答案
如果两个数组都已排序,则只需向前跳过一个迭代器或另一个或两者(如果存在匹配项)。
所以像这样:
void printUnion(int* a, int aSize, int* b, int bSize)
{
int *aEnd = a + aSize, *bEnd = b + bSize;
std::vector<int> unionVec;
for (; a != aEnd; ) {
if (b == bEnd) {
// copy all of a
while (a != aEnd) {
unionVec.push_back(*a);
a = std::upper_bound(a + 1, aEnd, *a);
}
break;
}
if (*b < *a) {
unionVec.push_back(*b);
b = std::upper_bound(b + 1, bEnd, *b);
}
else {
unionVec.push_back(*a);
if (*b == *a) {
b = std::upper_bound(b + 1, bEnd, *b);
}
a = std::upper_bound(a + 1, aEnd, *a);
}
}
// copy all of b
while (b != bEnd) {
unionVec.push_back(*b);
b = std::upper_bound(b + 1, bEnd, *b);
}
printVector(unionVec);
}
如果不能直接使用upper_bound
,就自己实现那个函数吧。从 this reference 复制实现:
template<class ForwardIt, class T>
int* upper_bound(int* first, int* last, const int value)
{
int* it;
int count = last - first;
int step;
while (count > 0) {
it = first;
step = count / 2;
it += step;
if (value >= *it) {
first = ++it;
count -= step + 1;
}
else {
count = step;
}
}
return first;
}
或者非二进制搜索版本:
int* upper_bound(int* first, int* last, const int value) {
for (; first < last && *first == value; ++first) {
;
}
return first;
}
现在这显然非常冗长,这就是标准实际上直接为您提供算法的原因 set_union :
void printUnion(int* a, int aSize, int* b, int bSize)
{
std::vector<int> unionVec;
// get the union
std::set_union(a, a + aSize, b, b + bSize, std::back_inserter(unionVec));
// remove the dupes
unionVec.erase(std::unique(unionVec.begin(), unionVec.end()), unionVec.end());
printVector(unionVec);
}
关于arrays - 查找 2 个排序数组的并集(有重复项),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27239996/