java - Time limit exceeded even with best approach(Java)

Question

Even if I think that I solved a competitive programming problem from HackerEarth with the best approach, all tests exceed the time limit. I really do not know how to optimize it further because it is just an easy exercise.

My approach: iterate over all array members than add them to a HashMap which stores their occurrences. After that simply read the query numbers and get their occurence from the HashMap.

This is my solution:

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);
            }
        }
    }
}

My question is: what can be the problem with my approach? Why does it run out of time?

标签： java

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();
    }
}  

是的，我知道这很奇怪，练习本身并没有那么难，但是读取输入并写出结果是其中很大一部分。