Hackerrank動態數組超時

我正在研究Hackerrank上的數據結構跟蹤，當時我遇到了這個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(); 
} 
}

我的問題是：是什麼在這裏，解決差異超時問題？我的第一個猜測是數組比ArrayLists需要更長的時間訪問/更改元素。是這樣嗎？

來源

2017-02-09 murdoc1871

可能不是。「ArrayList」較慢的一點是如果您知道所需的大小，但不是使用正確的構造函數預先分配大小，而是使用默認大小創建大小。當添加很多東西時，ArrayList需要調整自己的大小，這可能是緩慢的原因。訪問元素時沒有明顯的速度差異（而且數組反而會更快，而不是相反）。 – Kayaman

我看關鍵的區別是，在不良的執行代碼，你給每個內ArrayList<Integer>的n的初始大小，而在其他代碼你只給地，初始尺寸到外部列表：

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

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

我猜這是一個錯誤，並迫使每個內部列表中有大小n你正在做的內存空間R由此算法O(n²)所確定。

來源

2017-02-09 21:25:04 StriplingWarrior

Hackerrank動態數組超時

回答

相關問題