配列内に3つ以上の等しいオブジェクトがありますか？

Question

私は問題につまずいた、多分誰かが私にそれを解決する方法のポインタを与えることができますか？

だから、私は（私たちは、彼らがリスト内のリストだと仮定することができます）オブジェクトの配列を持っているので、そのようなことを前提とすることができます：

{ {1,2}, {2}, {1,2}, {3,4,5}, {1,2} } 

オブジェクト内の要素はありません例えば（一度だけ表示されます私はオブジェクトリストから2つの等しいオブジェクトしか必要としないと思う前に、問題をうまく処理しましたが、今はもっと必要となり、配列を通るブルートフォースが本当に痛いようになりました。 {1,2}のトリプルクワッドループなどで醜いメソッドを作成しなくてもいいですか？

Thあなたは

Answer 1

簡単な方法は、キーがオブジェクトであり、値がカウントの整数であるマップを使用することです。この方法で、あなたはそれをより早く見つけることができます。衝突のないハッシュマップに対してはO（nlogn）またはO（kn）。

擬似コード（正確なメソッドのシグネチャを覚えていますが、アイデアを得ることができない）：

for (object o : myObjs) 
{ 
    int num = 0; 
    if (map.containsKey(o)) { 
     map.put(o, map.get(o) + 1); 
     num = map.get(o); 
    } else { 
     map.put(o, 1); 
     num = 1; 
    } 
    if (num == 3) 
     System.out.println("Object " + o + " has 3 members in set"); 
} 

Answer 2

あなたが好きなほぼすべてのコンパレータの実装を使用して配列をソートすることができますが、それが等しくなるように論理的に等しいオブジェクトをレポート提供しました。また、ソートされた配列をリニアスキャンして3つ以上のランを見つけることは簡単です。

Answer 3

イエス・ラモスの答えに基づいて構築された基本的な考え方は、各サブリストを繰り返し、含まれている要素が何回表示されているかを把握することです。

#include <vector> 
using std::vector; 
#include <map> 
using std::map; 

// input data 
typedef vector<int> List; 
typedef vector< int, List > ListOfLists; 
ListOfLists input; 

// temporary map for keeping track of how many times we see 
// individual elements. if you have boost or TR1, you can 
// use unordered_map for a (possibly substantial) speedup. 
typedef map< int, int > OccuranceMap; 
OccurranceMap seen; 

// now loop through all the sub-lists 
for (ListOfLists::const_iterator outer = input.begin(), 
            oend = input.end(); 
     outer != oend; ++outer) 
{ 
    // and then iterate through all elements in each sublist 
    for (List::const_iterator inner = (*outer).begin(), 
           iend = (*outer).end(); 
      inner != iend; ++inner) 
    { 
     // and keep track of how many we've seen. using 
     // operator[] is very slightly inefficient, but 
     // shouldn't matter unless you have zillions of 
     // distinct values. 
     ++seen[*inner]; 
    } 
} 

// finally, go through the list of occurances and find those 
// that showed up 3 times (or more than 3, depends on your 
// application of course; just change the conditional). 
for (OccuranceMap::const_iterator ci = seen.begin(), 
            cend = seen.end(); 
     ci != cend; ++ci) 
    if ((*ci).second == 3) 
     cout << "saw '" << (*ci).first << "'" 
      << " " << (*ci).second << " times" << endl; 

は、個々のサブリストがあるどのくらいに応じて、これはさらに、ダブルループだけで重複を見つけるために、より良い選択かもしれません。このトレードオフは、出現回数の余分なメモリ容量です。