在两个整数列表之间连续选择较大的数字

Question

我一直在尝试制作一个概念简单的 Python 代码，但我一直未能弄清楚如何使用优雅的代码来做到这一点。

基本上，给定两个按升序排列的整数列表：

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

从列表 A 开始，我想将连续列表（A-B-A-B-A。因此）中的下一个更高的数字合并到空列表 C 中。

在执行中，这会产生

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

并以 122 结束，因为我们在列表 A 中找不到更高的数字。

Answer 1

您可以利用 itertools.cycle 在两个列表之间切换。一旦你能做到这一点，你就可以使用 filter() 从当前迭代器中获取下一个更大的值，并跟踪迄今为止看到的最大值。

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]

如果您知道 A 不会为空，您可以稍微简化一下。

Answer 2

定义一个函数get_index获取下一个较大元素的索引，然后依次追加元素，其中sig用于区分A和B列表的顺序：


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]

Answer 3

我们可以加入列表并在它们之间触发。

如果您希望得到一些只使用很少元素的巨大列表，二分搜索方法（已注释）可能比线性扫描更好。

#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)

在两个整数列表之间连续选择较大的数字

Picking larger numbers in succession between two list of integers

python

sorting

algorithm

list