1. ホーム
  2. java

[解決済み] 配列内の整数の最頻値を求める

2022-02-11 01:27:07

質問

この問題では、整数の配列の中で最も頻出する要素を返す mode というメソッドを書くことになっている。配列には少なくとも1つの要素があり、配列の各要素は0から100までの値を持つと仮定する。同値の場合は低い方を選択すること.

例えば、渡された配列に {27, 15, 15, 11, 27} という値が含まれている場合、このメソッドは 15 を返す必要があります。(ヒント: この章の前のほうにある Tally プログラムを見て、この問題の解き方のアイデアを得るとよいでしょう)。

特定の入力に対して何が問題になっているのかがわからず困っています。たとえば、次のようなことです。

mode({27, 15, 15, 27, 11, 11, 14, 15, 16, 19, 99, 100, 0, 27}) は正しい 15 を返しますが、 mode({1, 1, 2, 3, 3}) は 1 でなければならないのに 3 を返します。

以下はそのコードです。

public static int mode(int[] input) {
    int returnVal = input[0]; // stores element to be returned
    int repeatCount = 0; // counts the record number of repeats
    int prevRepCnt = 0; // temporary count for repeats

    for (int i=0; i<input.length; i++) { // goes through each elem

        for (int j=i; j<input.length; j++) { // compares to each elem after the first elem

            if (i != j && input[i] == input[j]) { // if matching values
                repeatCount++; // gets the repeat count

                if (repeatCount>=prevRepCnt) { // a higher count of repeats than before
                    returnVal=input[i]; // return that element
                }
                prevRepCnt = repeatCount; // Keeps the highest repeat record
            }
            repeatCount=0; // resets repeat Count for next comparison
        }
    }
    return returnVal;
}

解決方法は?

この問題を解くより簡単な方法を紹介します。サイズ101のcountという配列を作成します。インデックス(0-100)は、数える数字を表します。入力配列を走査して、各数字の出現回数を数えます。最後に、カウントを比較して、最も多く出現する数字を見つけます(同数の場合は小さい数字が選ばれます)。

public static int mode(int[] input) {

    int[] count = new int[101];

    //count the occurrences
    for (int i=0; i < input.length; i++) {
        count[input[i]]++;
    }

    //go backwards and find the count with the most occurrences
    int index = count.length-1;
    for (int i=count.length-2; i >=0; i--) {
        if (count[i] >= count[index])
            index = i;
    }

    return index;
}