Hackerrankダイナミックアレイタイムアウト

Question

私はこれを見つけたときにHackerrankのData Structuresトラックで作業していましたchallenge。

私のコードはうまくいくと思いますが、タイムアウトの問題が発生しています。つまり、多くのクエリを使用して入力を実行するには時間がかかりすぎているようです。ここで（タイムアウトの問題で）ソリューションでの私の最初のショットは、次のとおりです。ここで

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(); 
} 
} 

私の質問は：違いが解決することをここにある何タイムアウトの問題？私の最初の推測では、配列はArrayListsよりも要素のアクセスや変更に時間がかかります。これは本当ですか？

Answer 1

他のコードの中であなただけの外側のリストにその初期サイズを与えているのに対し、私が見る主な違いは、下手に実行するコードでは、あなたがnのArrayList<Integer>各内側の初期サイズを与えているということです：私はこれが間違いだった推測している、とサイズを持つように、内側の各リストを強制することにより、あなたはメモリ空間rを作っているn

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

対

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

このアルゴリズムO(n²)に等しい。