k回以上存在するリスト内のすべての要素を見つける最良の方法

Question

私はちょうど問題に出くわしたので、これを解決する最善の方法が何か不思議でした。

私はLの大きさを想定すると、リスト

L = [[1, 2, 3, 4, 5, 6, 7], [2, 4, 6, 8, 10, 12], [3, 6, 9, 12, 15], ....] 

の一覧をK回以上では、存在するすべての要素を見つけるための最善の方法をどのようになるかN、されていL？

たとえば、k = 2の場合は、 [2, 3, 4, 6, 12]と表示されます。

Answer 1

Lのサイズをnとすると、Lでk回以上存在するすべての要素を見つける最良の方法は何ですか？

伝統的な方法は、各リストを1回ずつ反復し、時刻値をHashMap<Integer, Integer>（キーは数値、値は時間）に収集することです。 、 OK：

public static List<Integer> getResultListByMap(List<List<Integer>> inputList, int k) { 
    Map<Integer, Integer> times = new HashMap<>(); 
    for (List<Integer> integers : inputList) { 
     for (Integer integer : integers) { 
      if (times.keySet().contains(integer)) { 
       times.put(integer, times.get(integer) + 1); 
      } else { 
       times.put(integer, 1); 
      } 
     } 
    } 

    List<Integer> result = new ArrayList<>(); 
    for (Map.Entry<Integer, Integer> entry : times.entrySet()) { 
     if (entry.getValue() >= k) { 
      result.add(entry.getKey()); 
     } 
    } 
    return result; 
} 

resultリストは、リストk回以上

UPDATEに提示されているすべての数字が含まれています。次に、あなただけの値がk以上あるマップからすべてのキーを収集する必要があります私はあなたがすでにHashMapのアプローチを使用していることがあり、それはあなたのために遅いです。 2000個の要素（今は半分だけを取ると2000のリスト - サイズを2000 x 2000問題のために倍の速

public static List<Integer> getResultListBySort(List<List<Integer>> inputList, int k) { 
    List<Integer> newList = inputList.parallelStream() 
      .flatMap(l -> l.parallelStream()).sorted().collect(Collectors.toList()); 

    List<Integer> result = new ArrayList<>(); 

    Integer prev = null; 
    int sum = newList.get(0); 
    for (Integer integer : newList) { 
     if (integer.equals(prev)) { 
      sum++; 
     } else { 
      if (sum >= k) { 
       result.add(integer); 
      } 
      sum = 1; 
     } 
     prev = integer; 
    } 
    return result; 
} 

それは次のとおりです。私は、並べ替え、リストの連結を使用し、並列処理からボーナスを獲得するJava 8ストリームAPI機能を備えたアルゴリズムを書きました第二は、（それは完全にそれはOで結果を見つけるために、大丈夫です、あなたがたまには、この操作を行っている検討するL.上で実行される動作の周波数に依存

Benchmark      Mode Samples Score Score error Units 
c.c.b.MyBenchmark.testMap  avgt  20 0,972  0,030 s/op 
c.c.b.MyBenchmark.testSorted avgt  20 0,534  0,005 s/op 

Answer 2

）私のPC上の結果のリストを取得するにはn_1 + n_2 + n_3 + ... + n_n）時間複雑さ。すなわち、アレイの配列を反復してカウントすることによって毎回見つける。頻繁に操作する場合は、配列の配列をソートしないでください。なぜキャッシュを使用しないのでしょうか。私は最良の方法はあなたの使い方に完全に依存すると信じています。

Answer 3

完全に横断された要素の数を格納する余分なカウント配列を維持します。次に、要素の数を更新しながらリストをトラバースし、要素の数がkに等しい場合に更新中に、最初は空の最終回答リストに追加します。しかし、これを行うには、与えられた配列内にある最大要素を知っている必要があります。

final_answer = [] 
count = [0 for i in range(max_el)] # put very large number here e.g. 1000 
for sublist in L: 
    for element in sublist: 
     count[element] += 1 
     if count[element] == k: 
      final_list.append(element) 

あなたは*配列の配列をプリント（final_answer）