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动态数组超时

回答

相关问题