Suppose I have the following array:
1, 4, 5, 2, 3
I need to rearrange it to
5, 1, 4, 2, 3
There is only on extra space; one int
.
I figured one solution to solve it. But it is O(n^2)
complexity.
Can anyone offer a faster solution?
Thanks
Edited: sorry, not rotating array.
I need to change original array to result array. The order can be arbitrary. I just need to make A -> B. B is been told to me.
thanks
Edited 2"
Make it clearer. Array B is not fixed. We need to find a general solution for this.
Updated:
Thank you all. Seems like this is a brain teaser question. haha :D
My friend been asked by Amazon interviewer for this. LOL
B
is given to you, why do you need to recreate it from A - Shahbaz 2012-04-03 23:45
This solution works using O(1) space.
>>> def arrayswap(source, dest):
... for i in range(len(dest)):
... source[source.index(dest[i])], source[i] = source[i], source[source.index(dest[i])]
...
>>> a = [1, 4, 5, 2, 3]
>>> b = [5, 1, 4, 2, 3]
>>> arrayswap(a, b)
>>> a
[5, 1, 4, 2, 3]
Without using python's tuple packing, the value of one of source[i] or source[source.index(dest[i])] could be stored in an int.
source.index(dest[i])
you mean a linear search? That would give O(n^2)
performanc - Shahbaz 2012-04-03 23:50
a,b = b,a
fwenom 2012-04-03 23:51
It seems to me that this is just a special case of sorting the array, where the sort order is rather arbitrary. So, an optimal algotithm would have time complexity O(n log n), and using one that does in-place sorting (at the expense of not being a stable sort) would have space complexity O(1). An in-place merge sort would fit the bill, as would an in-place quicksort if average O(n log n) is OK.
a = a + b; b = a - b; a = a - b;
In general, if $
and #
are operators such that a $ b # b = a
and a $ b = b $ a (same with #)
then you can write a = a$b; b=a#b; a = a#b;
One interesting example is xor for both $ and # - Shahbaz 2012-04-03 23:48
O(0)
Esailija 2012-04-03 23:58
O
notation comes from), you don't think about a
and b
being loaded in registers. Saying a = a+b
does not require extra space. In practice though that's not the case as we all know it - Shahbaz 2012-04-03 23:58
0
is O(0)
because there exists a c > 0
(say 1) where 0 < c*0
for all input sizes n > 0
. Note that we are talking about memory, not time - Shahbaz 2012-04-03 23:59
0 <= c*0
. As for the space, yes, and I guess ninjagecko's point was the practice, not the theory - Daniel Fischer 2012-04-04 00:04
a = a^b
method was used for example) (think of a turing machine to see where that extra memory comes from). Since nobody counts these extra memory, I thought you could skip the data registers also - Shahbaz 2012-04-04 00:09
O(0)
by a dose of practice. I may be wrong, of course - Daniel Fischer 2012-04-04 00:15
a+b
overflows, the underflow from a-b
fixes it. After all, addition and subtraction are congruent modulo 2^32 (if 32 bit) and in the end the numbers would be right. Still, that's another reason for people to choose xor to other operators. (P.S. BugFix: in my first comment, a $ b = b $ a (same with #)
doesn't need to hold - Shahbaz 2012-04-04 08:39
It seems like you are just moving the first three elements to the left (with a wrap around).
So, ignore the index 3 and 4.
int temp = array[0]
array[0] = array[1]
array[1] = array[2]
array[2] = temp
You can just do:
temp = arr[0];
arr[0] = arr[2];
arr[2] = arr[4];
arr[4] = arr[1];
arr[1] = arr[3];
arr[3] = temp;
To rearrange array a to be as array b, you can just do like this:
for (var i = 0; i < a.length; i++) {
for (var j = i + 1; a[i] != b [i]; j++) {
var temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Demo: http://jsfiddle.net/Guffa/5sKdM/
I'm not sure what the big-O is on this one, but with the example data it does 7 comparisons and 2 swaps, so that is definitely better than O(n2).
Also, I'm not sure exactly what counts as an "extra space", so I don't know if this fulfills the requirement of the one extra space, but if it doesn't, neither does the currently accepted answer...