godzilaa
BAN USERpublic static int[] a14486004(int n, int[][] arr) {
int[] seq = new int[n * n];
int x = 0;
int y = 0;
int indx = 0;
boolean dir = true;
int d = 1;
int d1 = 0;
for (int i = 0; i < 2 * n - 1; i++) {
int s = x - y;
if (s<0){
s *= -1;
}
for (int j = 0; j < s; j++) {
seq[indx] = arr[y][x];
if (dir) {
x++;
y--;
} else {
x--;
y++;
}
indx++;
}
seq[indx] = arr[y][x];
indx++;
if (s == n - 1) {
d = 0;
d1 = 1;
}
if (dir) {
x += d;
y += d1;
} else {
x += d1;
y += d;
}
dir = dir ? false : true;
}
return seq;
}
How can you do it in O(log n)? and worst case is O(nlog n) for sure. Every time you check the number you insert and search from a binary search tree having complexity of search O(log n). you would have searched n times if you found the second number at index n. so O(nlog n).
- godzilaa January 09, 2012
What is the complexity going to be? As far as i can see this is going to be expensive compared to first solution. When you i initialize the Sum array, its going to take O((m-k)*(n-k)) time to initialize it..
- godzilaa August 15, 2012