1

次のようなテーブルがあるとします: (テーブルは C++ では 2 次元配列です) number は各行のカウントです。

1 a b c
1 a b c
1 c d e
1 b c d
1 b c d

に絞られる：

2 a b c
1 c d e
2 b c d

私のアルゴリズムは O(n*n) ですが、誰かがそれを改善できますか?

suppose t1 is original one;
initial another t2;
row_num = 1;
copy first row of t1 to t2;

foreach row in t1 (1 to n)
    search each row in t2 (0 to row_num);
        if equal, then add the number;
            break;
    if not found, then copy current t1's row to t2;
        row_num++
4

2 に答える 2

2

例のようにデータが並べ替えられている場合は、O（n）だけです。

std :: sort（またはその他のO（nlogn）sort）を使用して、配列を並べ替えます。その後、それはちょうど別のパスであり、それは行われます:)

于 2013-01-18T07:54:04.327 に答える
0

O(N log N)これが複雑さの実例です。最初にデータを並べ替え、次に各要素をループして、最初の不一致を探し、現在の要素からのカウントの合計を結果ベクトルに格納することにより、発生数をカウントします。初期配列で1とは異なるカウントを持つこともできることに注意してください。std::arrayすでに辞書式順序が設定されているため、特定の比較関数を指定しなくてもコードは機能しますoperator<。

以下のコードは、コンパイラで機能しない可能性のあるC ++ 11機能（auto、lambda）を使用しています。イナタイライザーリストを使用して1つのステートメントでベクトルを初期化することもできますが、intとarrayのペアのネストされたベクトルを使用すると、中括弧をいくつ書く必要があるかについて少し混乱しました:-)

#include <algorithm>
#include <array>
#include <iostream>
#include <utility>
#include <vector>

typedef std::pair<int, std::array<char, 3> > Element;
std::vector< Element > v;
std::vector< Element > result;

int main()
{
        v.push_back( Element(1, std::array<char, 3>{{'a', 'b', 'c'}}) );
        v.push_back( Element(2, std::array<char, 3>{{'a', 'b', 'c'}}) );
        v.push_back( Element(1, std::array<char, 3>{{'c', 'd', 'e'}}) );
        v.push_back( Element(1, std::array<char, 3>{{'b', 'c', 'd'}}) );
        v.push_back( Element(3, std::array<char, 3>{{'b', 'c', 'd'}}) );

        // O(N log(N) ) complexity
        std::sort(v.begin(), v.end(), [](Element const& e1, Element const& e2){
                // compare the array part of the pair<int, array>
                return e1.second < e2.second; 
        });

        // O(N) complexity
        for (auto it = v.begin(); it != v.end();) {
                // find next element
                auto last = std::find_if(it, v.end(), [=](Element const& elem){
                        return it->second != elem.second;     
                });

                // accumulate the counts
                auto count = std::accumulate(it, last, 0, [](int sub, Element const& elem) {
                    return sub + elem.first;
                });

                // store count in result
                result.push_back( Element(count, it->second) );                  
                it = last;
        }

        for (auto it = result.begin(); it != result.end(); ++it) {
                std::cout << it->first << " ";
                for (std::size_t i = 0; i < 3; ++i)
                        std::cout << it->second[i] << " ";
                std::cout << "\n";
        }
}

Ideoneの出力

注：並べ替えられた要素のループはO(N^2)（線形std::find_ifの中にネストされた線形for）に見えるかもしれませんが、これは、すでに検索された要素をスキップするO(N)最後のループステートメントが原因です。it = last

于 2013-01-18T08:38:33.013 に答える