Почему я получаю сообщение об ошибке "прекращено из-за таймаута" для моего кода в hackerrank?

Я получил "Прервано из-за ошибки тайм-аута", когда я запускал свой код только для некоторых конкретных тестовых случаев. Хотя мой код успешно скомпилирован для других тестовых случаев. Может кто-нибудь помочь мне с этим?

Ссылка - https://www.hackerrank.com/challenges/phone-book

Постановка задачи :

Вам дают телефонную книгу, которая состоит из имен людей и их номера телефона. После этого вам будет дано имя человека в качестве запроса. Для каждого запроса выведите номер телефона этого человека.

Формат ввода:

В первой строке будет целое число, обозначающее количество записей в телефонной книге. Каждая запись состоит из двух строк: имя и соответствующий номер телефона.

После этого будут некоторые запросы. Каждый запрос будет содержать имя человека. Читайте запросы до конца файла.

Ограничения:

1 <= N <= 100000

1 <= Запрос <= 100000

Имя человека состоит только из строчных букв английского алфавита и может быть в формате "имя-фамилия" или в формате "имя-имя". Каждый номер телефона имеет ровно 8 цифр без начальных нулей.

Выходной формат :

Для каждого случая выведите "Не найдено", если у человека нет записи в телефонной книге. В противном случае напечатайте имя человека и номер телефона. Смотрите пример выходных данных для точного формата.

Чтобы облегчить проблему, мы предоставили часть кода в редакторе. Вы можете либо завершить этот код, либо написать полностью самостоятельно.

Мой код выглядит следующим образом:

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

class Solution
{
 public static void main(String []args)
 {
  Scanner in = new Scanner(System.in);
  int n=in.nextInt();
  in.nextLine();
  ArrayList<String> name = new ArrayList<String>();
  int[] phone = new int[100000];

  for(int i=0;i<n;i++)
  {
   name.add(in.nextLine());
   phone[i]=in.nextInt();
   in.nextLine();
  }

  while(in.hasNext())
  {
   String s=in.nextLine();
   int a=name.indexOf(s);

   if(a>=0)
   {
    System.out.println(s + "=" + phone[a] );
   }
   else
   {
    System.out.println("Not found");
   }
  }
 }
}

PS: это мой первый вопрос на форуме. Я любитель изучения Java. Извините, если я нарушил любое из многих правил, задаваемых вопросом :(. Пожалуйста, исправьте меня и помогите мне внести свой вклад в сообщество здесь хорошим способом :)

Ответ 1

Проблема с вашей логикой заключается в том, что она реализована с использованием ArrayList, которая является последовательной структурой. Любой поиск в Списке будет последовательным, и для больших тестовых примеров потребуется слишком много времени для поиска в списке имен.

Карта хэшей более подходит для примера телефонной книги, поскольку она хранит данные в ключе, парах значений и поиске вверх быстро из-за хэширования

Вот версия, которая реализована с использованием HashMap

   Map<String,Integer> phonebook = new HashMap<>();
  Scanner in = new Scanner(System.in);
  int n=in.nextInt();
  in.nextLine();
  for(int i=0;i<n;i++)
  {
     String name=in.nextLine();
     int phone=in.nextInt();
     in.nextLine();
      phonebook.put(name,phone);
  }
  while(in.hasNext())
  {
     String s=in.nextLine();
     Integer phone = phonebook.get(s);
     if(phone==null){
         System.out.println("Not found");
     } else {
         System.out.println(s+"="+phone);
     }
  }

Надеюсь, что это объяснит.

Ответ 2

Обычно "Завершение из-за ошибки таймаута" происходит, когда ваш код занимает больше времени для выполнения, чем максимальное время, заданное диспетчерами проблем (Hackerrank).

Задача, которую вы пытаетесь научить тому, как используются HashMaps, но вы решили проблему с использованием массивов. Поиск в массивах занимает O (n) больше времени, чем у карт, которые обычно хэшируются для поиска в O (1) времени. Для меньшего ввода ваша программа работает нормально, но для больших входов, таких как 100000 записей, потребуется больше времени и приведет к тайм-ауту. Так что используйте карты вместо массивов и массивов.

Ответ 3

Я не получаю никаких ошибок, подобных твоим. Кроме того, единственная причина, по которой ваш код не проходит тест, заключается в том, что вы пишете Found в верхнем регистре, а не Found на lowecase, как и ожидалось.

Удачи.