java - 即使使用最佳方法也超出了时间限制(Java)

Question

即使我认为我解决了竞争性编程problem from HackerEarth使用最好的方法，所有测试都会超过时间限制。我真的不知道如何进一步优化它，因为这只是一个简单的练习。

我的方法:迭代所有数组成员，然后将它们添加到存储它们的出现次数的 HashMap 中。之后，只需读取查询编号并从 HashMap 中获取它们的出现情况即可。

这是我的解决方案:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

class TestClass {

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        //go through all test cases
        for (int i = 0; i < t; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            String[] inputs = br.readLine().split(" ");
            int N = Integer.parseInt(inputs[0]);
            int Q = Integer.parseInt(inputs[1]);
            inputs = br.readLine().split(" ");

            //read array
            for (int j = 0; j < N; j++) {
                int x = Integer.parseInt(inputs[j]);
                Integer value = map.get(x);
                //if number is already in hashmap then increment its count
                //else put it into the map with a count of 1
                if (value == null) {
                    map.put(x, 1);
                } else map.put(x, value + 1);
            }

            //iterate through the queries and get their occurences from the map
            for (int j = 0; j < Q; j++) {
                int x = Integer.parseInt(br.readLine());
                Integer value = map.get(x);
                if (value == null) {
                    System.out.println(0);
                } else System.out.println(value);
            }
        }
    }
}

我的问题是:我的方法可能存在什么问题？为什么会超时？

Answer 1

好吧，所以问题并不是那么明显。我查看了输入文件，它们很大，因此您必须使用一些非常快速的方法来写入控制台(许多测试用例->>许多答案)。您可以使用 PrinteWriter 来实现此目的。

工作解决方案:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

class TestClass {

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pr = new PrintWriter(System.out);
        int t = Integer.parseInt(br.readLine());

        //go through all test cases
        for (int i = 0; i < t; i++) {
            Map<Integer, Integer> map = new HashMap<>();
            String[] inputs = br.readLine().split(" ");
            int N = Integer.parseInt(inputs[0]);
            int Q = Integer.parseInt(inputs[1]);
            inputs = br.readLine().split(" ");

            //read array
            for (int j = 0; j < N; j++) {
                int x = Integer.parseInt(inputs[j]);
                Integer value = map.get(x);
                //if number is already in hashmap then increment its count
                //else put it into the map with a count of 1
                if (value == null) {
                    map.put(x, 1);
                } else map.put(x, value + 1);
            }

            //iterate through the queries and get their occurences from the map
            for (int j = 0; j < Q; j++) {
                int x = Integer.parseInt(br.readLine());
                Integer value = map.get(x);
                if (value == null) {
                    pr.println(0);
                } else pr.println(value);
            }
        }
        pr.close();
    }
}  

是的，我知道练习本身并不难，这很奇怪，但读取输入并写出结果才是其中的重要部分。