Sort one sequence by O(n) in time and O(1) in space
nispray at gmail.com
Sun Feb 9 15:40:38 CET 2014
Yes, with no new list, otherwise, space won't to be O(1)
2014年2月9日 下午10:31于 "Oscar Benjamin" <oscar.j.benjamin at 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 <nispray at gmail.com> wrote:
> > 2014年2月9日 下午9:41于 "Oscar Benjamin" <oscar.j.benjamin at gmail.com>写道：
> >> On 9 February 2014 12:13, Wesley <nispray at 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:
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-list