Java 为什么我的代码在hackerrank上会收到“因超时而终止”错误？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/37230853/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why do i get a "terminated due to timeout" error for my code at hackerrank?
提问by Swaggerboy
I got a "Terminated due to timeout error" when i ran my code for some specific testcases only. Even though my code compiled successfully for other testcases. Can someone please help me with this?
当我仅针对某些特定测试用例运行代码时，出现“由于超时错误而终止”。即使我的代码为其他测试用例成功编译。有人可以帮我解决这个问题吗？
Link -https://www.hackerrank.com/challenges/phone-book
链接 - https://www.hackerrank.com/challenges/phone-book
Problem Statement :
问题陈述 ：
You are given a phone book that consists of people's names and their phone number. After that you will be given some person's name as query. For each query, print the phone number of that person.
您将获得一个电话簿，其中包含人们的姓名和电话号码。之后，您将获得某个人的姓名作为查询。对于每个查询，打印该人的电话号码。
Input Format:
输入格式：
The first line will have an integer denoting the number of entries in the phone book. Each entry consists of two lines: a name and the corresponding phone number.
第一行将有一个整数，表示电话簿中的条目数。每个条目由两行组成：姓名和相应的电话号码。
After these, there will be some queries. Each query will contain a person's name. Read the queries until end-of-file.
在这些之后，会有一些查询。每个查询将包含一个人的姓名。读取查询直到文件结束。
Constraints:
约束：
1<=n<=100000
1<=n<=100000
1<=Query<=100000
1<=查询<=100000
A person's name consists of only lower-case English letters and it may be in the format 'first-name last-name' or in the format 'first-name'. Each phone number has exactly 8 digits without any leading zeros.
一个人的名字仅由小写英文字母组成，可以采用“first-name last-name”格式或“first-name”格式。每个电话号码正好有 8 位数字，没有任何前导零。
Output Format :
输出格式 ：
For each case, print "Not found" if the person has no entry in the phone book. Otherwise, print the person's name and phone number. See sample output for the exact format.
对于每种情况，如果此人在电话簿中没有条目，则打印“未找到”。否则，打印此人的姓名和电话号码。有关确切格式，请参阅示例输出。
To make the problem easier, we provided a portion of the code in the editor. You can either complete that code or write completely on your own.
为了使问题更容易，我们在编辑器中提供了一部分代码。您可以完成该代码，也可以完全自己编写。
My code is as follows :
我的代码如下：
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:This is my first question on the forum. I'm an amateur learning java. Sorry if i violated any of the many rules of asking a question :( . Please do correct me and help me contribute to the community here in a good way :)
PS：这是我在论坛上的第一个问题。我是一个学习java的业余爱好者。对不起，如果我违反了提问的许多规则中的任何一条:(。请纠正我并帮助我以一种好的方式为社区做出贡献:)
采纳答案by Sanjeev
The problem with your logic is that it is implemented using ArrayListwhich is a sequential structure. Any search in List will be sequential and for large test cases its taking too much time to lookup in your names list.
您的逻辑的问题在于它是使用ArrayList顺序结构实现的。List 中的任何搜索都将是连续的，对于大型测试用例，在您的姓名列表中查找需要花费太多时间。
Hash map is more appropriate for a phone book example as it keeps data in key, value pair and look ups are fast because of hashing
散列映射更适合电话簿示例，因为它将数据保存在键值对中，并且由于散列，查找速度很快
Here is a version that is implemented using HashMap
这是一个使用 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);
}
}
Hope this explains.
希望这能解释。
回答by UDKOX
I am no getting any errors like yours. Also, the only reason why your code doesn't pass the test is because you spelled Foundon uppercase instead of foundon lowecase as it's expected.
我没有像你这样的错误。此外，您的代码未通过测试的唯一原因是因为您拼写Found了大写而不是found预期的小写。
Have fun.
玩得开心。
回答by Chirram Kumar
Usually "Terminated due to timeout error" occurs when your code takes longer time to execute than the maximum time set by the Problem Setters(Hackerrank).
当您的代码执行时间超过问题设置者（Hackerrank）设置的最长时间时，通常会发生“因超时错误而终止”。
The problem you tried is intended to teach you how HashMaps are used, but you solved the problem using arrays. Searching in arrays takes O(n)longer time than that of Maps which are generally hashed to search in O(1) time. For smaller input your program works fine, but for larger inputs like 100000 entries, It will take longer time and result in time out. So Use Maps instead of Arrays and ArrayLists
您尝试的问题旨在教您如何使用 HashMap，但您使用数组解决了问题。在数组中搜索比通常在 O(1) 时间内进行散列搜索的 Map 花费 O(n) 更长的时间。对于较小的输入，您的程序运行良好，但对于较大的输入，例如 100000 个条目，将花费更长的时间并导致超时。所以使用 Maps 而不是 Arrays 和 ArrayLists
