0

我有三个向量

vector<string> usersA = {"a15_afd","a19_afd","a20_afd"}
vector<string> usersB = {"b15_afd","b26_afd","b98_afd"}
vector<string> usersC = {"c94_afd","c92_afd","c99_afd"}

我想检查字符 a 之后的数字是否存在于其他向量中。示例：usersA 索引 0 是 a15_254，我想检查其他向量 usersB 或 usersC 中是否存在 15。

同样，我必须检查 b 和 c 之后的数字是否存在于其他向量中。到目前为止我做了什么。将数字存储到特定向量中

     vector<string> usersANumber;  // it has the numbers of usersA {"15","19","20"}
     vector<string> usersBNumber;  // it has the numbers of usersB {"15","26","98"}
     vector<string> usersCNumber;  // it has the numbers of usersC {"94","92","99"}

我有三个for循环第一个循环我检查userANumber的数量是否存在于其他两个向量中，第二个循环我检查usersBNumber的数量是否存在于其他两个向量中，第三个循环我检查usersCNumber的数量是否存在在另外两个向量中

我觉得这效率不高。有没有其他方法可以做到这一点

4

1 回答 1

0

将数字存储到新向量中后，您只需对这些向量进行排序，然后使用二分搜索算法搜索重复项：

vector<string> usersA = { "15", "19", "20" };
vector<string> usersB = { "15", "26", "98" };
vector<string> usersC = { "94", "92", "99" };

sort(usersA.begin(), usersA.end());
sort(usersB.begin(), usersB.end());
sort(usersC.begin(), usersC.end());

searchForDuplicateItems(usersA, usersB);
searchForDuplicateItems(usersA, usersC);
searchForDuplicateItems(usersB, usersC);

请注意，您只需要比较一次向量，即在遍历向量usersA的所有项目后检查它们是否存在于向量usersB中，无需遍历向量usersB的所有项目以检查它们是否存在于向量usersA中。

searchForDuplicateItems函数实现如下图所示：

void searchForDuplicateItems(vector<string> &v1, vector<string> &v2)
{
    for (int i = 0; i < v1.size(); i++)
    {
        if (vectorContainsItem(v2, v1[i]))
        {
            // duplicate item found
        }
    }
}

这里是vectorContainsItem函数的实现，它内部使用了二分查找算法来提高效率：

bool vectorContainsItem(vector<string> &v, string &item)
{
    int left = 0;
    int right = (int) v.size() - 1;
    int mid = (right + left) / 2;

    while (left <= right)
    {
        mid = (right + left) / 2;
        if (v[mid].compare(item) == 0)
            return true;
        else if (v[mid].compare(item) < 0)
            left = mid + 1;
        else if (v[mid].compare(item) > 0)
            right = mid - 1;
    }

    return false;
}
于 2013-10-20T12:53:34.487 回答