Hackerrank Java Map Вопрос Вопрос Тайм-аут

Question

Я решил проблему с картой Java, но у меня был результат тайм-аута для 2 случаев. Когда я изменил только проблему printf, проблема решена. Однако я не мог понять, почему это так? Вот мой код:

import java.util.*;
import java.io.*;

class Solution{

private static HashMap<String, Integer> phoneBook = new HashMap<>();
public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    String search = "";

    int n=in.nextInt();
    in.nextLine();
    for(int i=0; i<n; i++) {
        String name=in.nextLine();
        int phone=in.nextInt();
        phoneBook.put(name, phone);
        in.nextLine();
    }

    while(in.hasNext()) {
        search = in.nextLine();
        if (phoneBook.get(search) != null)
            System.out.printf(search + "=" + phoneBook.get(search) + "\n"); // this works 
            // System.out.printf("%s=%d\n", search, phoneBook.get(search)); // this does not work why ?
        else
            System.out.println("Not found");  
    }
}

Answer 1

Когда вы выполняете форматирование вывода, java анализирует строку для форматирования ("%s=%d\n" в вашем случае), чтобы поместить значения вместо заполнителей. Требуется как минимум O(n) сложность, что важно в вашем случае.

Также вы звоните phoneBook.get(search) дважды. Попробуйте сохранить результат в переменной. Это также может ускорить программу.

Answer 2

Formatter.format() занимает время

Formatter.format() (и его ярлык System.out.printf()) требует анализа, проверки и форматирования.Все это занимает огромное количество времени.

Так что просто выведите данные как можно быстрее.Hackerrank требует от вас создавать быстрые программы, так что просто сделайте это: быстрая программа.Объединяйте свои элементы вместо их форматирования.Кроме того, если у вас нет параметров, просто используйте System.out.println() вместо System.out.printf.

Answer 3

Краткий ответ: производительность поиска в Hashmap + Форматирование извлеченного значения из HashMap было в вычислительном отношении более интенсивным, чем просто конкатенация строки без какого-либо формата.

Чтобы быть немного многословным, реализация HashMap, которая разработана для амортизированной сложности O (1) для функций get (Key), имеет неприятную сложность O (n) ( подчеркивая термин наихудший случай:) ) если все или большинство ключей имеют общий хеш. Такие случаи, хотя и не очень распространенные, произошли бы, когда фидер тестовых наборов дал огромный ввод тестового набора с несколькими повторяющимися значениями. Такая ситуация в сочетании с одновременным форматированием привела бы к сбою.

Answer 4

Чтобы разбить строку на отдельные строки, нам нужно использовать спецификатор% n в выражении printf.

System.out.printf("%s=%d%n", search, phoneBook.get(search));

ИЛИ вы можете использовать String.format (), показанный в приведенном ниже утверждении.

System.out.println(String.format("%s=%d",s,p));