performance - 特定范围内最常见的数字

Question

首先：在你降级这不是我的作业之前，这个问题属于codingbat或eulerproject或其他网站。我不是要你给我一个完整的和编码的答案我是要你给我一些想法来帮助我。

后来，我遇到了这个问题的时间限制问题。我实际上解决了它，但我的解决方案太慢了。它需要在 0 到 1 秒内完成。在最坏的情况下，我的代码消耗超过 8 秒。如果您可以帮助我提出一些想法，或者您可以向我展示更准确的解决方案伪代码等。我将不胜感激。

第一个输入意味着我们要处理多少次。稍后，用户输入两个数字[X, Y], (0 < X < Y < 100000)我们需要计算这两个数字 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