Yes, with no new list, otherwise, space won't to be O(1) Wesley 2014年2月9日 下午10:31于 "Oscar Benjamin" <oscar.j.benja...@gmail.com>写道：
> Please reply to the list rather than directly to me so that other > people can see the answer to my question and offer you help. > > On 9 February 2014 14:04, Ni Wesley <nisp...@gmail.com> wrote: > > 2014年2月9日 下午9:41于 "Oscar Benjamin" <oscar.j.benja...@gmail.com>写道： > > > >> On 9 February 2014 12:13, Wesley <nisp...@gmail.com> wrote: > >> > Hi guys, > >> > Here is one question related to algorithm. > >> > Details here: > >> > > >> > here is input sequence like a1,a2,...,an,b1,b2,...,bn ，the ax and bx > >> > always exist in pair. So, now, how to change the sequence to > >> > a1,b1,...,an,bn, with time complexity as O(n) and space as O(1). > >> > >> Do you mean that you have a list and you want to rearrange the > >> elements in-place without creating a new list? > > > > Yes > > Okay so if you're going to do it with O(1) space then it's going to > have to be done with a whole bunch of swaps. Have a think with pen and > paper about how you could do a sequence of swaps that would rearrange > the order to the one that you want (it's actually a harder problem > than it looks at first glance). This is an example of what is known as > "transposition" and much information is available about algorithms for > doing this in-place: > http://en.wikipedia.org/wiki/In-place_matrix_transposition > > > Oscar >
-- https://mail.python.org/mailman/listinfo/python-list
