-2

問題に遭遇したばかりで、これを解決する最善の方法は何かと考えていました。

リストのリストがあります

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

Lのサイズがnであると仮定すると、 Lにk回以上存在するすべての要素を見つける最良の方法は何でしょうか?

たとえば、 の場合k = 2、 を取得する必要があります [2, 3, 4, 6, 12]。

4

3 に答える 3

3

L のサイズが n であると仮定すると、L に k 回以上存在するすべての要素を見つける最良の方法は何でしょうか?

従来の方法では、各リストを 1 回反復し、時間の値を収集しますHashMap<Integer, Integer>(キーは数値、値は時間)。k次に、値が以上であるマップからすべてのキーを収集するだけです。

 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。

更新: OK、私はあなたHashMapがすでにアプローチを使用していることを知っていますが、それはあなたにとって遅いです。リストの連結、並べ替えを使用し、並列処理からボーナスを得る Java 8 Stream API 機能を備えたアルゴリズムを作成しました。

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;
}

2000 個の2000 x 2000要素を含む 2000 個のリスト (現在、私の PC で結果リストを取得するのに 0.5 秒しかかかりません)

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
于 2016-03-29T14:50:18.463 に答える
0

これは、L に対して実行される操作の頻度に完全に依存します。この操作をたまに行うと考えてください。O(n_1+n_2+n_3+...+n_n) 時間の複雑さで結果を見つけることは問題ありません。つまり、配列の配列を反復してカウントすることにより、毎回見つけます。頻繁な操作の場合は、配列の配列を並べ替えたり、キャッシュを使用したりしないでください。最善の方法は、あなたの使い方に完全に依存すると思います。

于 2016-04-07T20:43:29.660 に答える
0

完全にトラバースされた要素の数を格納する追加の count 配列を維持します。次に、要素の数を更新しながらリストをトラバースし、要素の数が 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)

print(最終回答)

于 2016-05-16T17:15:08.390 に答える