How to implement such an algorithm: we find max from the list, add it to another list, delete it immediately, then find min, also add it to another list and delete it immediately. Constantly throws an error out of the array (made through pop)

  • one
    show the code with the error - splash58
  • for i in range (len (a)): b.append (max (a)) a.pop (max (a)) b.append (min (a)) a.pop (min (a)) I know that the jamb is that the length changes, but how to fix it - I don’t quite understand - user1337157
  • Why cycle? What are ab and new? and write the code in question - splash58
  • And how then without a cycle? Go through len (a) // 2? The meaning is as follows: Added> deleted, added> deleted - user1337157
  • maximum sheet one, at least, too, why they are many times somewhere to add and remove. Well, if several times, then why search for several times - splash58

2 answers 2

O(n log n) in time, O(n) in memory algorithm:

 from math import ceil a = [2, 3, 1, 5, 4] a.sort(reverse=True) middle = ceil(len(a) / 2) a[::2], a[1::2] = a[:middle], a[middle:][::-1] print(a) # -> [5, 1, 4, 2, 3]

O(n log n) in time, O(1) in memory algorithm:

 from collections import deque a = [2, 3, 1, 5, 4] a.sort() q = deque() while a: q.append(a.pop()) while q: a.append(q.popleft()) if q: a.append(q.pop()) print(a) # -> [5, 1, 4, 2, 3]

O(n**2) in time, O(1) in memory algorithm:

 a = [2, 3, 1, 5, 4] b = [] odd = False while a: b.append(a.pop((min if odd else max)(range(len(a)), key=a.__getitem__))) odd = not odd print(b) # -> [5, 1, 4, 2, 3]

    functional solution:

     In [200]: import math In [201]: from itertools import zip_longest, chain In [202]: l = sorted(a, reverse=True) In [203]: b = [x for x in chain.from_iterable(zip_longest(l[:math.ceil(len(l)/2)], l[::-1][:len(l)//2])) if x] In [204]: b Out[204]: [7, 6, 7, 6, 7]

    if at all "in the forehead":

     In [169]: a = [6,6,7,7,7]; In [170]: l = sorted(a, reverse=True) ...: b = [] ...: while l: ...: b.append(l.pop(0)) ...: if l: ...: b.append(l.pop(len(l)-1)) ...: In [171]: b Out[171]: [7, 6, 7, 6, 7]
    • 2
      Current terrible for replace with while l: - splash58
    • @ splash58, thanks, that's more like it! :) - MaxU
    • Thank you very much! - user1337157