0

与えられたintの配列で最も多く発生する数を見つけようとしています。これが私のコードです、それは動作しますが、いくつかの矛盾があります。また、どうすれば改善できるか教えていただければ、コードが長すぎると思います!!

public static int countOccurrences(int[] a, int x) {
    int count = 0;
    for(int i=0;i<a.length;i++) {
        if(a[i] == x) count++;
    }
    return count;
}

public static int occursMostOften(int[] a) {
    int[] count = new int[a.length];
    boolean[] duplicate = new boolean[a.length];
    for(int i = 0; i < a.length;i++) {
        if(duplicate[i] != true) {
            count[i] = countOccurrences(a,a[i]);
            duplicate[i] = true;
        }
    }
    return a[maxIndex(count)];
}
private static int maxIndex(int[] a) {
    int max = 0;
    for(int i = 1; i<a.length;i++) {
        if(a[i-1]<a[i]) max = i;
    }
    return max;     
}
4

2 に答える 2

2

これが割り当てである場合 (そうであると思います)、コードは要件を満たしていますが、最適ではありません。

Map と呼ばれるデータ構造について学習している場合は、代わりにそれを使用してください。マップのキーは配列の値になり、マップの値はこの値を見た回数になります。

これにより、コードの複雑さが軽減されます。一連の操作は次のとおりです。

配列内の各値に対して

  1. 値がマップに存在する場合は、カウントを更新します
  2. そうでない場合は、カウントが 1 の新しいエントリを作成します

最後に、マップを反復処理して、最も多く発生する値を見つけることができます。

于 2012-07-31T10:05:09.467 に答える
0

コードは、重複していない数値ごとに配列全体の線形スキャンを実行します。n異なる値を持つサイズの配列をn使用すると、コードの複雑さが O(n^2) になります。

次のアルゴリズムを使用すると、O(n) でより適切に実行できます。

  • 配列内のすべての数値を反復処理します
  • 数値ごとに、数値を保持するマップ ( ) に追加し、Map<Integer, Integer>カウントします。
  • number がマップに存在する場合、現在のカウントを取得し、インクリメントして、マップに戻します
  • 番号が存在しない場合は、そのエントリをカウント 1 でマップに入力するだけです
  • すべての反復が完了したら、値とフィンの最大値を取得します。
于 2012-07-31T10:07:23.117 に答える