Reorganizing an array with O (1) extra memory is faster than O (n ^ 2)
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 extra space; one int
.
I ended up solving one solution. But this is the complexity O(n^2)
.
Can anyone suggest a faster solution?
thank
Edited: sorry, not a rotating array.
I need to change the original array to an array of results. The order can be arbitrary. I just need to do A -> B. B was told.
thank
Edited 2 "
Make it clearer. Array B is not fixed. We need to find a general solution for this.
Updated:
Thanks everyone. Sounds like it's a brain teaser question. haha: D
A friend of mine asked an Amazon interviewer for this. Lol
source to share
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 tuple packing, the value of one of the sources [i] or the source [source.index (dest [i])] can be stored in int.
source to share
It seems to me that this is just a special case of sorting an array, where the sort order is pretty arbitrary. Thus, the optimal algorithm will have time complexity O (n log n), and with a method that does sort in place (due to unstable sort), it will have space complexity O (1). In place of merge sort will match the score, as in place of quicksort , if average O (n log n) is ok.
source to share
You can simply do:
temp = arr[0];
arr[0] = arr[2];
arr[2] = arr[4];
arr[4] = arr[1];
arr[1] = arr[3];
arr[3] = temp;
Edit:
To reorder array a as array b, you can simply do the following:
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, but with the example data, it does 7 comparisons and 2 swaps, so it's definitely better than O (n 2 ).
Also, I'm not sure exactly what counts as "extra space", so I don't know if this requirement of extra space satisfies, but if it doesn't, then the currently accepted answer ...
source to share