8

C++ にベクトル/配列があり、これらの N 要素のどれが最大の反復回数を持っているかをカウントし、最高のカウントを出力したいとします。このジョブに最適なアルゴリズムはどれか。

例：

int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}

2 が 4 回発生するため、出力は 4 です。これが 2 が発生する最大回数です。

4

9 に答える 9

18

配列を並べ替えてから、クイック パスを実行して各数値をカウントします。アルゴリズムの複雑さは O(N*logN) です。

または、数値をキーとしてハッシュ テーブルを作成します。キーを設定した各要素のカウンターをハッシュテーブルに格納します。1 回のパスですべての要素を数えることができます。ただし、アルゴリズムの複雑さは、ハッシュ関数の複雑さに依存するようになりました。

于 2008-09-28T09:44:55.953 に答える
10

スペースに最適化：

次に、クイックソート（たとえば）は、最大数のみを追跡しながら、アイテムを反復処理します。せいぜいO（N log N）。

速度に最適化：

個別のカウントを追跡しながら、すべての要素を繰り返し処理します。このアルゴリズムは常にO（n）になります。

于 2008-09-28T10:17:17.123 に答える
4

RAMがあり、値が大きすぎない場合は、countingsortを使用します。

于 2008-09-28T10:47:35.943 に答える
2

STLを利用する可能性のあるC++実装は次のとおりです。

#include <iostream>
#include <algorithm>
#include <map>

// functor
struct maxoccur
{
    int _M_val;
    int _M_rep;

    maxoccur()
    : _M_val(0),
      _M_rep(0)
    {}

    void operator()(const std::pair<int,int> &e)
    {
        std::cout << "pair: " << e.first << " " << e.second << std::endl;
        if ( _M_rep < e.second ) {
            _M_val = e.first;
            _M_rep = e.second;
        }
    }
};

int
main(int argc, char *argv[])
{
    int a[] = {2,456,34,3456,2,435,2,456,2};
    std::map<int,int> m; 

    // load the map
    for(unsigned int i=0; i< sizeof(a)/sizeof(a[0]); i++) 
        m [a[i]]++;

    // find the max occurence...
    maxoccur ret = std::for_each(m.begin(), m.end(), maxoccur());
    std::cout << "value:" << ret._M_val << " max repetition:" << ret._M_rep <<  std::endl;

    return 0;
}
于 2008-09-28T10:49:35.410 に答える
1

少しの疑似コード:

//split string into array firts
strsplit(numbers) //PHP function name to split a string into it's components
i=0
while( i < count(array))
 {
   if(isset(list[array[i]]))
    {
      list[array[i]]['count'] = list + 1
    }
   else
    {
      list[i]['count'] = 1
      list[i]['number']
    }
   i=i+1
 }
usort(list) //usort is a php function that sorts an array by its value not its key, Im assuming that you have something in c++ that does this
print list[0]['number'] //Should contain the most used number
于 2008-09-28T09:46:02.207 に答える
1

ハッシュ アルゴリズム (build count[i] = #occurrences(i) in 基本的に線形時間) は非常に実用的ですが、プロセス中にハッシュの衝突が発生する可能性があるため、理論的に厳密には O(n) ではありません。

この質問の興味深い特殊なケースは多数決アルゴリズムです。このアルゴリズムでは、配列エントリの少なくとも n/2 に存在する要素が存在する場合、その要素を見つけます。

これは簡単な説明であり、線形時間でこれを行う方法のより詳細な説明です。ハッシュのトリッキーさはありません。

于 2008-09-28T20:26:52.247 に答える
0

それはO(n)の中にあるだろう…………しかし、事は大きな数です。of 配列は同じサイズの別の配列を取ることができます........

for(i=0;i

mar=count[o]; インデックス=o;

for(i=0;i

次に、出力は次のようになります........要素インデックスは、最大数に対して発生します。この配列の回数.......

ここで a[] は、特定の番号の最大出現数を検索する必要があるデータ配列です。配列で.......

count[] 各要素のカウントを持ちます........ 注：データの範囲が配列になることはすでにわかっています..たとえば、. その配列内のデータの範囲は 1 から 100 までです........次に、100 要素のカウント配列を保持して、インデックス付きの値を 1 ずつ増加させて発生した場合....

于 2009-03-23T04:29:24.783 に答える
0

を使用した完全なテスト済みバージョンを次に示しstd::tr1::unordered_mapます。

これをほぼO(n)にします。最初に n 個の入力値を反復処理して のカウントを挿入/更新しunordered_map、次にpartial_sort_copyO(n) を実行します。2*O(n) ~= O(n)。

#include <unordered_map>
#include <vector>
#include <algorithm>
#include <iostream>

namespace {
// Only used in most_frequent but can't be a local class because of the member template
struct second_greater {
    // Need to compare two (slightly) different types of pairs
    template <typename PairA, typename PairB>
    bool operator() (const PairA& a, const PairB& b) const
        { return a.second > b.second; }
};
}

template <typename Iter>
std::pair<typename std::iterator_traits<Iter>::value_type, unsigned int>
most_frequent(Iter begin, Iter end)
{
    typedef typename std::iterator_traits<Iter>::value_type value_type;
    typedef std::pair<value_type, unsigned int> result_type;

    std::tr1::unordered_map<value_type, unsigned int> counts;

    for(; begin != end; ++begin)
        // This is safe because new entries in the map are defined to be initialized to 0 for
        // built-in numeric types - no need to initialize them first
        ++ counts[*begin];

    // Only need the top one at this point (could easily expand to top-n)
    std::vector<result_type> top(1);

    std::partial_sort_copy(counts.begin(), counts.end(),
                           top.begin(), top.end(), second_greater());

    return top.front();
}

int main(int argc, char* argv[])
{
    int a[] = { 2, 456, 34, 3456, 2, 435, 2, 456, 2 };

    std::pair<int, unsigned int> m = most_frequent(a, a + (sizeof(a) / sizeof(a[0])));

    std::cout << "most common = " << m.first << " (" << m.second << " instances)" << std::endl;
    assert(m.first == 2);
    assert(m.second == 4);

    return 0;
}
于 2008-11-18T05:19:43.937 に答える
0

要素の範囲が要素の数と比較して大きい場合、他の人が言ったように、並べ替えてスキャンするだけです。これは時間 n*log n であり、追加スペースはありません (おそらく log n 追加)。

カウントソートの問題は、値の範囲が大きい場合、ソートよりもカウント配列の初期化に時間がかかる可能性があることです。

于 2008-09-28T16:47:37.670 に答える