We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I have a question about whether we should use Array of ArrayList, or just 2D array.
I have my own code below
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int lastans =0;
int N = sc.nextInt();
int Q = sc.nextInt();
int tag, x, y, index;
ArrayList<Integer>[] list = new ArrayList[N];
while(Q-->0){
tag = sc.nextInt();
x = sc.nextInt();
y = sc.nextInt();
index = (x^lastans)%N;
switch (tag) {
case 1:
if (list[index] == null) {
ArrayList<Integer> myList = new ArrayList<>();
myList.add(y);
list[index] = myList;
} else
list[index].add(y);
break;
case 2:
System.out.println(lastans = list[index].get(y % list[index].size()));
break;
}
}
}
static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tok = null;
public static void main(String[] args) {
int last = 0, x, y;
int n = getInt(), q = getInt(), cmd, c, len;
int[][] A = new int[n][];
int[] tmp;
for(int k = 0; k < q; ++k) {
cmd = getInt();
x = getInt();
y = getInt();
c = (x^last) % n;
switch(cmd) {
case 1:
if(A[c] == null)
len = 1;
else
len = A[c].length + 1;
tmp = new int[len];
if(A[c] != null)
System.arraycopy(A[c], 0, tmp, 0, A[c].length);
tmp[tmp.length-1] = y;
A[c] = tmp;
break;
case 2:
System.out.println(last = A[c][y % A[c].length]);
}
}
}
static String gets() throws IOException{
if(tok == null || !tok.hasMoreTokens())
tok = new StringTokenizer(br.readLine());
return tok.nextToken();
}
static int getInt() {
try {
return Integer.parseInt(gets());
} catch(IOException | NumberFormatException e) {
return -1;
}
}
}
When I used array of ArrayList, I spent twice more time as using 2D array. Yes, I use ArrayList, but ArrayList.get(index) only needs constant time like array. And @__spartax used System.arraycopy, which requires O(n), which is exactly how ArrayList works when it has to expand its size. But he expanded the size everytime.
Yes, I have a higher space complexity because of ArrayList, but I don't get it why my algo spends twice time as his.
Thanks in advance.
Dynamic Array
You are viewing a single comment's thread. Return to all comments →
I have a question about whether we should use Array of ArrayList, or just 2D array.
I have my own code below
public class Solution {
}
And code from @__spartax:
public class Solution {
}
When I used array of ArrayList, I spent twice more time as using 2D array. Yes, I use ArrayList, but ArrayList.get(index) only needs constant time like array. And @__spartax used System.arraycopy, which requires O(n), which is exactly how ArrayList works when it has to expand its size. But he expanded the size everytime. Yes, I have a higher space complexity because of ArrayList, but I don't get it why my algo spends twice time as his. Thanks in advance.