java - Hackerrank 动态数组超时

Question

当我发现这个 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 需要更长的时间来访问/更改元素。是这样吗？

Answer 1

我看到的主要区别是，在性能不佳的代码中，您给每个内部 ArrayList<Integer>初始大小为n ，而在其他代码中，您仅将初始大小赋予外部列表:

group[thing] = new ArrayList<Integer>(n);

对比

group.add(new ArrayList<Integer>());

我猜这是一个错误，并通过强制每个内部列表的大小 n您正在创建此算法所需的内存空间 O(n²) .