0

したがって、2 つの 2d ベクトルがあり、vector1 は最初の行に共通の値を持ち、vector2 は 2 番目の列に共通の値を持ちます。vector1 の最初の行の値に従って、vector2 の行を並べ替えたいと思います。これを行う最良の方法は何ですか？

これは私がこれまでに得たものですが、ソートアルゴリズムでこれをより適切に行う方法があるかどうか疑問に思っています:

for(unsigned int i = 1; i < vec2.size(); i++)
    if(vec2[i][1] != vec1[0][i])
        swap(vec2[i], vec2[i + 1]);
4

1 に答える 1

0

簡単な解決策は次のとおりです。

std::vector<std::vector<int>> v1 = {
    { 3, 6, 4 },
    { 1, 1, 1 },
    { 1, 1, 1 }
};
std::vector<std::vector<int>> v2 = {
    { 1, 4, 1 },
    { 1, 6, 1 },
    { 1, 3, 1 }
};

const std::vector<int>& order = v1[0];

std::sort(v2.begin(), v2.end(), [&order](
    const std::vector<int>& r1, const std::vector<int>& r2) {
        auto it1 = std::find(order.begin(), order.end(), r1[1]);
        auto it2 = std::find(order.begin(), order.end(), r2[1]);
        return (it1 - it2) < 0;
});

ただし、このソリューションのコストは O(N^2 log N) と非常に高くなります。ベクトルのサイズによっては、これが問題になる場合とそうでない場合があります。

別のアプローチは、間接ベクトルとして中間ベクトルを使用することです。

std::vector<int> idxs(order.size());
for (std::size_t i = 0; i < order.size(); i++)
    idxs[i] = std::find(order.begin(), order.end(), v2[i][1]) - order.begin();

// After computing the intermediate vector you could access v2 like this:
v2[idxs[i]][j]

このソリューションには O(N^2) のコストがかかりますが、アクセスするたびにオーバーヘッドが発生しますv2。

最後に、独自の並べ替えソリューションを考え出すことができます。それでも、この問題を O(N^2) よりも小さいコストで解決することは不可能だと思います。

于 2012-07-12T10:33:43.957 に答える