Javaでは、最大値を見つけるためのアルゴリズムが必要です。整数のコレクション内の出現回数。たとえば、私のセットが[2,4,3,2,2,1,4,2,2]である場合、2はほとんど発生する整数であり、5回出現するため、アルゴリズムは5を出力する必要があります。整数のセットのヒストグラムのピークを見つけるようなものと考えてください。
課題は、多くの整数の複数のセットに対して1つずつ実行する必要があるため、効率的である必要があるということです。また、どの要素が主にセットに表示されるかはわかりません。それは完全にランダムです。
セットのそれらの値を配列に入れ、それをソートしてから配列を反復処理し、数字の連続した出現をカウントし、カウントの最大値を特定することを考えましたが、かなりの時間がかかると思います。それを効率的に行うのに役立つライブラリやアルゴリズムはありますか？
並べ替えの何が問題になっていますか？それはO（n log n）であり、まったく悪くはありません。より良い解決策は、入力セットに関するより多くの情報（おそらく、関係する数の上限）を必要とするか、Map<Integer, Integer>または同等のものを含むでしょう。
次のロジックを使用して、コレクションをループしてMapデータ構造に挿入します。
Javaには、HashMapとTreeMapの2つのマップがあります。これらを以下で比較します。
HashMapとTreeMap
必要に応じて、詳細な説明をスキップして、要約に直接ジャンプできます。
HashMapは、キーと値のペアを配列に格納するマップです。キーkに使用されるインデックスは次のとおりです。
2つの完全に異なるキーが同じインデックスになる場合があります。これを解決するために、配列内の各場所は実際にはリンクリストです。つまり、すべてのルックアップは常にリンクリストをループし、k.equals（other）メソッドを使用して等しいかどうかをチェックする必要があります。最悪の場合、すべてのキーが同じ場所に保存され、HashMapはインデックス付けされていないリストになります。
HashMapがより多くのエントリを取得すると、これらの衝突の可能性が高まり、構造の効率が低下します。これを解決するために、エントリの数がクリティカルポイント（コンストラクターのloadFactor引数によって決定される）に達すると、構造のサイズが変更されます。
ご覧のとおり、サイズ変更が多い場合、これは比較的コストがかかる可能性があります。
この問題は、開始する前に適切なサイズでHashMapを事前に割り当てることができれば、克服できます。たとえば、map = new HashMap（input.size（）* 1.5）です。大規模なデータセットの場合、これによりメモリチャーンを大幅に減らすことができます。
キーは基本的にHashMap内でランダムに配置されるため、キーイテレーターはランダムな順序でキーを反復処理します。Javaは、キーが挿入された順序で反復するLinkedHashMapを提供します。
HashMapのパフォーマンス：
OTOH a TreeMapは、エントリをバランスの取れたツリーに格納します。動的構造は、キーと値のペアが追加されるにつれて段階的に構築されます。挿入はツリーの深さ（log（tree.size（））に依存しますが、予測可能です。HashMapとは異なり、中断やパフォーマンスが低下するエッジ条件はありません。
十分に分散されたHashMapを考えると、各挿入とルックアップはより高価です。
さらに、キーをツリーに挿入するには、すべてのキーが他のすべてのキーと比較可能である必要があり、Comparableインターフェイスのk.compare（other）メソッドが必要です。明らかに、質問が整数に関するものであることを考えると、これは問題ではありません。
TreeMapのパフォーマンス：
概要
最初の考え：データセットのサイズ：
この特定のケースでは、重要な要素は、データセット全体のサイズと比較して、予想される一意の整数の数が多いか少ないかです。
上からの圧倒的なポイントがない場合の最後のポイント：
ただし、パフォーマンスが重要な場合、決定する唯一の方法は、Mapインターフェースに実装し、HashMapとTreeMapの両方をプロファイリングして、どちらが実際に状況に適しているかを確認することです。時期尚早の最適化は多くの悪の根源です:)
基本的な方法は、コレクションを並べ替えてから、並べ替えられたコレクションを実行することです。（これは、O（nLog（n））であるO（nLog（n）+ n）で実行されます）。
数値が制限されていて（たとえば、-10000,10000）、コレクションに多数の整数が含まれている場合は、ルックアップテーブルを使用して、各要素をカウントできます。これには、O（n + l）（カウントにはO（n）、最大要素を見つけるにはO（l））が必要です。ここで、lは範囲の長さ（この場合は20001）です。ご覧のとおり、n >> lの場合、これは1よりも優れたO（n）になりますが、n << lの場合、定数ですが、これを使用できなくするのに十分な大きさのO（l）になります。
前の別の変形は、ルックアップテーブルの代わりにHashTableを使用することです。これにより、O（n）の複雑さが改善されますが、n>>lの場合に2より高速であるとは限りません。良いニュースは、値を制限する必要がないことです。
私はあまりJavaではありませんが、これらのコーディングについてサポートが必要な場合は、お知らせください。
これがあなたのプログラムのサンプル実装です。最も頻度の高いnoが返され、出現回数が最大の2つのnoが見つかった場合は、大きい方のnoが返されます。頻度を返したい場合は、コードの最後の行を「returnmf」に変更します。
{public int mode(int[]a,int n)
{int i,j,f,mf=0,mv=a[0];
for(i=0;i<n;i++)
{f=0;
for(j=0;j<n;j++)
{if(a[i]==a[j])
{f++;
}
}
if(f>mf||f==mf && a[i]>mv)
{mf=f;
mv=a[i];
}
}
return mv;
}
}
この小さな子犬は機能します（数の代わりに頻度を返すように編集されています）：
public static int mostFrequent(int[] numbers) {
Map<Integer, AtomicInteger> map = new HashMap<Integer, AtomicInteger>() {
public AtomicInteger get(Object key) {
AtomicInteger value = super.get(key);
if (value == null) {
value = new AtomicInteger();
super.put((Integer) key, value);
}
return value;
}
};
for (int number : numbers)
map.get(number).incrementAndGet();
List<Entry<Integer, AtomicInteger>> entries = new ArrayList<Map.Entry<Integer, AtomicInteger>>(map.entrySet());
Collections.sort(entries, new Comparator<Entry<Integer, AtomicInteger>>() {
@Override
public int compare(Entry<Integer, AtomicInteger> o1, Entry<Integer, AtomicInteger> o2) {
return o2.getValue().get() - o1.getValue().get();
}
});
return entries.get(0).getValue().get(); // return the largest *frequency*
// Use this next line instead to return the most frequent *number*
// return entries.get(0).getKey();
}
AtomicIntegerは、増分ごとに新しいオブジェクトが作成されないようにするために選択され、コードは少しすっきりと読み取れます。
匿名マップクラスは、「ifnull」コードを一元化するために使用されました
テストは次のとおりです。
public static void main(String[] args) {
System.out.println(mostFrequent(new int[] { 2, 4, 3, 2, 2, 1, 4, 2, 2 }));
}
出力：
5
整数のコレクションなので、どちらも使用できます
ノート：
HashMapの使用：
import java.util.HashMap;
public class NumberCounter {
static HashMap<Integer,Integer> map;
static int[] arr = {1, 2, 1, 23, 4, 5, 4, 1, 2, 3, 12, 23};
static int max=0;
public NumberCounter(){
map=new HashMap<Integer, Integer>();
}
public static void main (String[] args)
{
Integer newValue=1;
NumberCounter c=new NumberCounter();
for(int i=0;i<arr.length;i++){
if(map.get(arr[i])!=null) {
newValue = map.get(arr[i]);
newValue += 1;
map.put(arr[i], newValue);
}
else
map.put(arr[i],1);
}
max=map.get(arr[0]);
for(int i=0;i<map.size();i++){
if(max<map.get(arr[i]))
max=map.get(arr[i]);
}
System.out.print(max);
}
}