ループと比較最適化

Question

I次のコードを持っている：

ArrayList<Integer> count = new ArrayList<>(); 
    for(int i=0;i<l.size();i++) 
     count.add(0); 

    for(int i=0;i<list.size();i++) 
    { 
     for(int j=0;j<l.size();j++) 
     { 
      if(list.get(i).equals(l.get(j))) 
      { 
       int val = count.get(j); 
       count.set(j, val+1); 
      } 
     } 
    } 

私の問題は、ループとの比較のための2つを実行するとき、それがループので、私が通過している反復処理しています、実行するのに非常に長い時間がかかることです：

プログラムを実行するのにかかる時間が短くなるように最適化する方法はありますか？

私はこれを見てきました：解決策は、私の場合には役立ちません。しかしfor loop optimizationと、より多くのページを。 「リスト」は数8の4倍と「L」が含まれている場合

--------- UPDATE ----------

比較は、整数値は、このためであります番号8が含まれている、カウンタは、しかし、私は個人的に、私はそれらを使用していない理由であるハッシュマップのが好きではない、4ハッシュマップが何に似て

にインクリメントする必要があります。

任意の助けいただければ幸いです。

Answer 1

私は、listの要素が何度表示されているのかを調べるために、lに表示しています。

そして、現在、あなたは（listがn要素を有し、lはmの要素を持っていると仮定して）複雑O(n * m)のだ、かなり素朴なソリューションを実装しました。

性能を向上させるために、あなたはあなたのソリューションの時間の複雑さを改善する必要があります。あなたは数がlに登場する回数を保持し、その後listの要素を反復しながら、それを使用しますHashMap<Integer, Integer>を作成することができます。

Map<Integer, Integer> map = new HashMap<>(); 
for (Integer i : l) { 
    map.put(i, map.getOrDefault(i, 0) + 1); 
} 

その後、listの各要素のために、あなただけの、その値がlに表示された回数を確認する必要があります。繰り返しますが、私はMapを使用します：

Map<Integer, Integer> count = new HashMap<>(); 
for (Integer value : list) { 
    Integer temp = count.get(value); 
    if (temp != null) { 
     count.put(value, temp + 1); 
    } else { 
     count.put(value, map.getOrDefault(value, 0) + 1); 
    } 
} 

HashMapを照会すると、一定時間（O(1)）を要するので、このソリューションは、はるかにはるかに優れてO(n * m)からであるO(n + m)複雑さ、で動作します。

しかし、問題の正確さやリストの内容は説明していないので、これらのスニペットは正確にはであるとは限りませんが、調整する必要がありますあなたの問題に対するこのアプローチ。