0

私は3つのベクトルを持っています

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"}

3 つの for ループがあります。最初のループでは、usersANumber の数が他の 2 つのベクトルに存在するかどうかを確認します。2 番目のループでは、usersBNumber の数が他の 2 つのベクトルに存在するかどうかを確認します。3 番目のループでは、usersCNumber の数が存在するかどうかを確認します。他の 2 つのベクトルで

これは効率的ではないと思います。私がこれを行うことができる他の方法はありますか

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);

ベクトルを 1 回比較するだけでよいことに注意してください。つまり、ベクトル 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 に答える