リスト内の基数10の出現数を最も多く見つけ出す

Question

以下の順序で同じ数字の出現数が最も多いのはどうすればわかりますか？

1,5,4,3,2,5,3,1,5,3,7,5,7 

この場合の答えは5です。

私はリストに各数字を追加する方向に傾いていて、数字が既にリストにある場合は、カウンターを増分します。この方法では、私はそれぞれの番号のためのカウンターを持っている必要があると思う。人が理解するのが最も簡単な解決策は何ですか？この場合

私はこれが動作していない試みであるJavaの

を使用しています：ステフの答えを若干修正

が、これは動作します -

public class Main { 

    public static void main(String args[]){ 

     int[] numbers = {1,5,4,3,2,5,3,1,5,3,7,5,7,7,7,7,7};   
     int[] counterArray = new int[numbers.length]; 

     for (int i = 0; i < numbers.length; ++i){ 
      counterArray[numbers[i]] = counterArray[numbers[i]] + 1; 
     } 

     int maxNumber = 0; 
     for (int i = 0; i < numbers.length; ++i){ 
      if(counterArray[i] > counterArray[maxNumber]) 
      { 
       maxNumber = i; 
      } 
     } 

     System.out.println(maxNumber); 
    } 

} 

Answer 1

これは、値が0から9の間になることを知っているときに、O（n）処理時間を与え、メモリフットプリント（あなたが既に持っている最初の配列を数えない）はO（1）です。counterArray = new int[10];過度のメモリ使用量を削減する

int[] numbers = {1,5,4,3,2,5,3,1,5,3,7,5,7}; 
//int[] counterArray = new int[10]; // use this if the max value of the in the array 'numbers' is known to be 9 
int[] counterArray = new int[numbers.length]; // Use this if the max value of the array is not known. 
// or we can quickly iterate O(n) operation to find the max value and use that 

for (int i = 0; i < numbers.length; ++i){ 
    counterArray[numbers[i]] = counterArray[numbers[i]] + 1; 
} 

int maxNumber = 0; 
for (int i = 0; i < numbers.length; ++i){ 
    if(counterArray[i] > countarArray[maxNumber]) 
    { 
     maxNumber = i; 
    } 
} 

Console.WriteLine("Number: " + maxNumber.ToString() + " occurs " + countarArray[maxNumber].ToString() + " times."); 

別の方法は、最小値と最大値用いO（n）を検索し、値の数（最小値によって配列位置をオフセットすることを忘れない合った配列を作成することであろう）。

Answer 2

アルゴリズムの一つ（ O（n）時間の複雑さとO（1）のメモリの複雑さ）：

あなたが言ったように、数字（10カウンター）を入力し、リストを一度スキャンします。 Cコード：

//int the_given_array[n]; 

int counter[10]; 
int ix, result; 
memset(counter,0,10); 

for(ix=0; ix<n; ix++) counter[the_given_array[i]]++; 

result = 0; 
for(ix=1; ix<10; ix++) if(counter[ix]>counter[result]) result = ix; 

アルゴリズム二（Oと（N^2）時間の複雑さとO（1）メモリの複雑性）：

注：あなたがある場合はこの1つは最初のものよりも利点がありません10進数の数字を処理してください！

現在のターゲット番号のカウンタを設定し、リストをスキャンしてカウントします。別の番号などを数えます。同じ数字の出現回数が最大になるようにしてください。リストを最大でn回スキャンする必要があります。速度を上げるために、GPUプログラミングを使用して各数値を並行して処理したいと思うかもしれません。

Answer 3

アルゴリズムが高速であることを願っているので、提案されたソリューションは確かに最速です。 0にサイズ10の配列を初期化し、その後、単に：

若干の平均タイムの最適化として

for (int i: arrayList) ++counterArray[i] 

、あなただけ見られる最も頻度の高い2つの数のランニングカウンタを維持することができ、最も一般的な場合には検索を停止2番目の最も一般的なものよりも前に数えています。ここで、はまだ検査されていない番号の数です。