为什么我在 hackerrank 上的代码会出现 "terminated due to timeout" 错误？

Question

当我运行我的代码仅用于某些特定的测试用例时，我得到了 "Terminated due to timeout error"。即使我的代码为其他测试用例编译成功。有人可以帮我吗？

Link - https://www.hackerrank.com/challenges/phone-book

问题陈述：

给你一本 phone 书，其中包含人名和他们的 phone 号码。之后你会得到一些人的名字作为查询。对于每个查询，打印那个人的 phone 号码。

输入格式 :

第一行将有一个整数，表示 phone 书中的条目数。每个条目由两行组成：一个名称和相应的 phone 编号。

在这些之后，会有一些疑问。每个查询都将包含一个人的名字。读取查询直到文件结束。

约束条件：

1<=n<=100000

1<=查询<=100000

人名仅由小写英文字母组成，格式可以是'first-name last-name'，也可以是'first-name'。每个 phone 数字恰好有 8 位数字，没有任何前导零。

输出格式：

对于每个案例，如果此人在 phone 书中没有条目，则打印 "Not found"。否则，打印此人的姓名和 phone 号码。有关确切格式，请参阅样本输出。

为了简化问题，我们在编辑器中提供了部分代码。您可以完成该代码或完全自己编写。

我的代码如下：

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。抱歉，如果我违反了提问的许多规则中的任何一条:(。请纠正我并帮助我以一种好的方式为这里的社区做出贡献:)

Answer 1

您的逻辑存在问题，它是使用顺序结构 ArrayList 实现的。 List 中的任何搜索都是顺序的，对于大型测试用例，在您的姓名列表中查找会花费太多时间。

散列映射更适合 phone 书籍示例，因为它将数据保存在键、值对中，并且由于散列

，查找速度很快

这里是使用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);
     }
  }

希望这能解释清楚。

Answer 2

通常 "Terminated due to timeout error" 当您的代码执行时间超过问题设置者 (Hackerrank) 设置的最长时间时会发生。

你试的这题本是教你HashMaps的用法，你却用数组解决了这个问题。在数组中搜索比通常在 O(1) 时间内散列搜索的 Maps 花费 O(n) 更长的时间。对于较小的输入，您的程序运行良好，但对于较大的输入（如 100000 个条目），它将花费更长的时间并导致超时。所以使用 Maps 而不是 Arrays 和 ArrayLists

为什么我在 hackerrank 上的代码会出现 "terminated due to timeout" 错误？

Why do i get a "terminated due to timeout" error for my code at hackerrank?

java

timeout

terminate