java - 配列内の最大繰り返し回数

Question

最小の時間複雑度A = [1,2,3,4,1,1]でJavaの配列の最大繰り返し頻度を見つける最速の方法は何 ですか?

ans = 1

どうすればこれを行うことができますか

Answer 1

（ほとんど）線形時間の解決策は、aを使用してHashMap<Integer, Integer>、Aに表示されるすべての値のヒストグラムを作成することです。

HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
for(int x : A)
{
    Integer v = m.get(x);
    if (null == v) {v = Integer.valueOf(0);}
    m.put(x, ++v);
}

マップ全体を調べて、最大値のエントリを返します。この方法では、entrySet()これも線形時間で行われます。