当我发现这个 challenge 时,我正在 Hackerrank 上的数据结构轨道上工作。 .
我认为我的代码可以工作,但遇到超时问题。也就是说,在具有大量查询的输入上运行似乎花费了太长时间。这是我的第一个解决方案(带有超时问题):
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
ArrayList<Integer>[] group = (ArrayList<Integer>[])new ArrayList[n];
int lastAns = 0;
ArrayList<Integer> curr = null;
//int currVal = 0;
for(int i = 0;i < q;i++){
int query = sc.nextInt();
int x = sc.nextInt();
int y = sc.nextInt();
int thing = (x^lastAns) % n;
if(query == 1){
if(group[thing] == null){
group[thing] = new ArrayList<Integer>(n);
}
curr = group[thing];
curr.add(y);
}else if(query == 2){
curr = group[thing];
lastAns = curr.get(y % curr.size());
System.out.println(lastAns);
}
}
sc.close();
}
}
这是没有超时问题的代码:
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
int lastAns = 0;
ArrayList<ArrayList> group = new ArrayList();
ArrayList<Integer> curr = null;
//int currVal = 0;
for (int i = 0; i < n; i++){
group.add(new ArrayList<Integer>());
}
for(int i = 0;i < q;i++){
int query = sc.nextInt();
int x = sc.nextInt();
int y = sc.nextInt();
int thing = (x^lastAns) % n;
if(query == 1){
curr = group.get(thing);
curr.add(y);
}else if(query == 2){
curr = group.get(thing);
lastAns = curr.get(y % curr.size());
System.out.println(lastAns);
}
}
sc.close();
}
}
我的问题是:解决超时问题的区别是什么?我的第一个猜测是数组比 ArrayList 需要更长的时间来访问/更改元素。是这样吗?
最佳答案
我看到的主要区别是,在性能不佳的代码中,您给每个内部 ArrayList<Integer>
初始大小为n
,而在其他代码中,您仅将初始大小赋予外部列表:
group[thing] = new ArrayList<Integer>(n);
对比
group.add(new ArrayList<Integer>());
我猜这是一个错误,并通过强制每个内部列表的大小 n
您正在创建此算法所需的内存空间 O(n²)
.
关于java - Hackerrank 动态数组超时,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42146905/