Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #65762

Re: Sort one sequence by O(n) in time and O(1) in space

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

Yes, with no new list, otherwise, space won't to be O(1)

Wesley
2014年2月9日 下午10:31于 "Oscar Benjamin" <oscar.j.benjamin@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@gmail.com> wrote:
> > 2014年2月9日 下午9:41于 "Oscar Benjamin" <oscar.j.benjamin@gmail.com>写道：
> >
> >> On 9 February 2014 12:13, Wesley <nispray@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
>

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 04:13 -0800
  Re: Sort one sequence by O(n) in time and O(1) in space Asaf Las <roegltd@gmail.com> - 2014-02-09 04:29 -0800
  Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-09 23:39 +1100
    Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:09 -0800
      Re: Sort one sequence by O(n) in time and O(1) in space Dave Angel <davea@davea.name> - 2014-02-09 22:00 -0500
  Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 13:41 +0000
  Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 14:30 +0000
  Re: Sort one sequence by O(n) in time and O(1) in space Ni Wesley <nispray@gmail.com> - 2014-02-09 22:40 +0800
  Re: Sort one sequence by O(n) in time and O(1) in space Roy Smith <roy@panix.com> - 2014-02-09 10:05 -0500
    Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-09 23:14 +0000
      Re: Sort one sequence by O(n) in time and O(1) in space Roy Smith <roy@panix.com> - 2014-02-09 19:15 -0500
      Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:26 -0800
        Re: Sort one sequence by O(n) in time and O(1) in space Sturla Molden <sturla.molden@gmail.com> - 2014-02-10 10:20 +0000
          Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve@pearwood.info> - 2014-02-11 05:20 +0000
            Re: Sort one sequence by O(n) in time and O(1) in space Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-12 11:56 +1300
          Re: Sort one sequence by O(n) in time and O(1) in space Tim Daneliuk <tundra@tundraware.com> - 2014-02-10 23:37 -0600
          Re: Sort one sequence by O(n) in time and O(1) in space Tim Daneliuk <tundra@tundraware.com> - 2014-02-10 23:37 -0600
        Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-10 21:37 +1100
        Re: Sort one sequence by O(n) in time and O(1) in space Sturla Molden <sturla.molden@gmail.com> - 2014-02-10 15:03 +0000
        Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-11 02:23 +1100
        Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-10 15:45 +0000
        Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-11 02:52 +1100
          Re: Sort one sequence by O(n) in time and O(1) in space Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-11 13:19 +1300
        Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-10 16:41 +0000
  Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 15:48 +0000
    Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:07 -0800
  Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-09 21:31 +0000

csiph-web