为什么我在hackerrank时收到代码的“由于超时而终止”错误?

2022-09-04 02:35:57

当我只为某些特定的测试用例运行代码时,我得到了一个“由于超时错误而终止”。即使我的代码已成功编译为其他测试用例。有人可以帮我吗?

链接 - 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

你的逻辑的问题在于它是使用顺序结构来实现的。List中的任何搜索都将是连续的,对于大型测试用例,在名称列表中查找需要花费太多时间。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,但是您使用数组解决了问题。在数组中搜索比Maps花费的时间长O(n)时间,Map通常被散列以在O(1)时间内搜索。对于较小的输入,程序工作正常,但对于较大的输入(如100000个条目),这将花费更长的时间并导致超时。因此,使用映射而不是数组和数组列表


推荐