performance - 特定の範囲の最多桁

Question

まず第一に、これは私の宿題ではありませんをダウングレードする前に、この質問はcodingbatまたはeulerprojectまたは別のWebサイトに属しています. 私は、完全に完成したコード化された回答を私に提供するようにあなたに求めているのではありません。

後で、この問題で時間制限の問題が発生しています。私は実際にそれを解決しましたが、私の解決策は遅すぎます。0～1秒以内で行う必要があります。最悪のシナリオでは、私のコードは 8 秒以上消費します。いくつかのアイデアを手伝ってくれたり、より正確なソリューションの疑似コードなどを見せてくれたりしたら、本当に感謝しています。

最初の入力は、処理する回数を意味します。後で、ユーザーが 2 つの数値[X, Y] (0 < X < Y < 100000)を入力します。この 2 つの数値 X と Y の範囲で最も頻繁に使用される桁を計算する必要があります ( Xと Y を含む) 。複数の数字の最大頻度は、それらの最小のものを印刷すると想定されるものと同じです。

説明する：

ユーザーが最初に入力するテスト ケースの数: 7

ユーザーが X と Y を入力 (最初のテスト ケース): 0 21

今、私は自分のソリューションですべての数字を開いたので、自由に使用できる別のアイデアがあるかもしれませんが、ヒントを与えるために: 0 1 2 3 ... (ここでは 10 を1として開く必要があります) のように数値を処理する必要があります0はすべて同じ) 1 0 1 1 1 2 1 3 ... 1 9 2 0 2 1 0 から 21 までの最も頻繁な桁を表示します(この場合: 1)

その他の例: (ソリューションを確認したい場合のテストケース)

X: 7 Y: 956結果: 1

X: 967 Y: 8000結果: 7

X: 420 Y: 1000結果: 5など

これまでの私のコードは次のとおりです。

package most_frequent_digit;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main
{
public static int secondP = 0;

public static void getPopularElement(int[] list)
{
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (Integer nextInt : list)
    {
        Integer count = map.get(nextInt);
        if (count == null)
        {
            count = 1;
        } else
        {
            count = count + 1;
        }
        map.put(nextInt, count);
    }

    Integer mostRepeatedNumber = null;
    Integer mostRepeatedCount = null;
    Set<Integer> keys = map.keySet();
    for (Integer key : keys)
    {
        Integer count = map.get(key);
        if (mostRepeatedNumber == null)
        {
            mostRepeatedNumber = key;
            mostRepeatedCount = count;
        } else if (count > mostRepeatedCount)
        {
            mostRepeatedNumber = key;
            mostRepeatedCount = count;
        } else if (count == mostRepeatedCount && key < mostRepeatedNumber)
        {
            mostRepeatedNumber = key;
            mostRepeatedCount = count;
        }
    }

    System.out.println(mostRepeatedNumber);
}

public static void main(String[] args)
{
    @SuppressWarnings("resource")
    Scanner read = new Scanner(System.in);
    int len = read.nextInt();

    for (int w = 0; w < len; w++)
    {
        int x = read.nextInt();
        int y = read.nextInt();
        String list = "";

        for (int i = x; i <= y; i++)
        {
            list += i;
        }
        String newList = "";

        newList += list.replaceAll("", " ").trim();
        int[] listArr = new int[list.length()];

        for (int j = 0; j < newList.length(); j += 2)
        {
            listArr[secondP] = Character.getNumericValue(newList.charAt(j));
            secondP++;
        }

        getPopularElement(listArr);
        secondP = 0;
    }
}
}

ご覧のとおり、ユーザーが X: 0 Y: 1000000 と入力すると、8 ～ 9 秒のように時間がかかりすぎます。しかし、それは1秒で答えを返すはずです。チェックしていただきありがとうございます...

Answer 1