Clever Geek Handbook

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

+3


source to share


4 answers


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.

+1


source


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.



+2


source


It looks like you are just moving the first three elements to the left (with a wrapper).

So, ignore indices 3 and 4.

  int temp = array[0]
  array[0] = array[1]
  array[1] = array[2]
  array[2] = temp
0


source


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 ...

-1


source






More articles:


All Articles