Picking larger numbers in succession between two list of integers

user_18339801 0
Viewed 113

I have been trying to make a Python code that is straightforward in concept but I have been unsuccessful at figuring out how to do so with an elegant code.

Basically, given two ascending-sorted lists of integers:

A = [5, 6, 7, 9, 35, 47, 88, 100] 
B = [3, 12, 44, 78, 94, 122, 186] 
C = []

Starting from list A, I want to bin the next higher number in a successive list (A-B-A-B-A. As such) into an empty list C.

In execution, this would produce

C = [5,12,35,44,47,78,88,94,100,122]

And end at 122, as we cannot find any number higher in list A.

list sorting algorithm python
3 Answers

You can leverage itertools.cycle to flip between the two lists. Once you can do this, you can use filter() to get the next larger value from the current iterator and keep track of the largest seen so far.

from itertools import  cycle

def get_seq(A, B):
    if not A:  # handle case where A is empty
        return
        
    its = cycle((iter(A), iter(B)))
    current_val = A[0] - 1

    for i in its:
        try:
            current_val = next(filter(lambda n: n > current_val, i))
        except StopIteration:
            return
        yield current_val
    
            
A = [5, 9, 35, 47, 88, 100] 
B = [3, 12, 44, 78, 94, 122, 186] 

list(get_seq(A, B))
# [5, 12, 35, 44, 47, 78, 88, 94, 100, 122]

If you know A won't be empty you can simplify this a bit.

user_38746230

Define a function get_index to get the index of the next larger element, and then append the elements in turn, where the sig is used to distinguish the order between the A and B lists：


def get_index(lst, value):
    for i in range(len(lst)):
        if lst[i] > value:
            return i


def solution(a, b):
    res, sig, index_a, index_b = [], True, 0, 0
    while True:
        if sig:
            if len(res):
                index_a = get_index(a, res[-1])
            item = a[index_a]
            res.append(item)
            if item >= b[-1]:
                break
            sig = False
        else:
            index_b = get_index(b, res[-1])
            item = b[index_b]
            res.append(item)
            if item >= a[-1]:
                break
            sig = True

    return res

A = [5, 6, 7, 9, 35, 47, 88, 100]
B = [3, 12, 44, 78, 94, 122, 186]

print(solution(A, B))
# [5,12,35,44,47,78,88,94,100,122]
user_168744660

We can join the lists and trigger between them.

If you expect some huge list with only few elements being used, binary search approach (commented) might be better than linear scan.

#import bisect

A = [5, 6, 7, 9, 35, 47, 88, 100]
B = [3, 12, 44, 78, 94, 122, 186]
AB = [A,B]
lens = [len(A), len(B)]
C = []
curr = [0, 0]
idx = 0
while curr[idx] < lens[idx]:
    val = AB[idx][curr[idx]]
    C.append(val)
    idx = 1 - idx

    #curr[idx] = bisect.bisect_right(AB[idx], val + 1, curr[idx] + 1)

    while curr[idx] < lens[idx] and AB[idx][curr[idx]] <= val:
        curr[idx] += 1

print(C)
user_8444160
Related