pythonlistmergealternate

Merging Unequal two lists alternatively


My goal is to write down a function that calls all the even-numbered indices will have the largest numbers in the list in descending order and the odd-numbered indices will have the smallest numbers in ascending order.

For example:

input: arr = [1,2,3,4,5]
output: arr = [5,1,4,2,3]

input: arr = [1,2,3,4,5,6,7]
output: arr = [7,1,6,2,5,3,4]

I'm splitting the original array into two different arrays. One for the even-indexed and the other one for the odd-indexed. Then I reversed the array with even-indexed numbers. My problem is to merge two unequal lists alternatively.

# This is my python code

def max_min_naive(lst):
    even_lst = []
    odd_lst = []

    for i in range(len(lst)):
        if i%2 == 0:
            even_lst.append(lst[i])
        else:
            odd_lst.append(lst[i])
    #print(even_lst, odd_lst)
    even_lst.reverse()
    #print(even_lst, odd_lst)

    even_pointer = 0
    odd_pointer = 0
    res = []

    #print(len(even_lst), len(odd_lst))

    #This part is wrong. need help

    while len(res) <= len(lst):
        if even_pointer < len(even_lst):
            res.append(even_lst[even_pointer])
            even_pointer += 1
        else:
            break
        if odd_pointer < len(odd_lst):
            res.append(odd_lst[odd_pointer])
            odd_pointer += 1
        else:
            break
    #print(res)
    return res

if __name__ == '__main__':
    lst = [1,2,3,4,5]
    lst_1 = [1,2,3,4,5,6,7]
    print(max_min_naive(lst))
    print(max_min_naive(lst_1))

I get [7,2,5,4,3,6,1] instead of [7,1,6,2,5,3,4]


Solution

  • I would break this apart some more. First off we know that we want a sorted array, so lets do that:

    arr = sorted(arr)
    

    Then we can break the list into the high numbers and low numbers:

    lower = arr[:len(arr) // 2]
    upper = arr[len(arr) // 2:]
    

    Now we want to populate a merged list. While there are items left, pop the higher from the end, and the lower from the start:

    merged = []
    while lower or upper:
        if upper:
            merged.append(upper.pop())
        if lower:
            merged.append(lower.pop(0))
    

    You'll be left with the desired result in merged.