交替合并不等长列表实现偶数位降序存大数奇数位升序存小数

核心问题 #

你现有代码的根本问题是前置逻辑不符合需求规则，并非合并逻辑有致命错误：

• 需求要求偶数索引位放原数组整体的较大值按降序排列，奇数索引位放原数组整体的较小值按升序排列，你原代码是直接拆分原数组的奇偶索引位置元素，完全不符合数据源要求，这是结果错误的核心原因。
• 你现有合并逻辑的终止条件len(res) <= len(lst)存在冗余，实际只需要判断两个指针是否都走完对应列表即可。

正确实现步骤 #

1. 先将原数组整体从小到大升序排序
2. 拆分排序后的数组为两部分：
   • 较大值段：取排序数组的后半段，长度为原数组长度向上取整的一半，反转后得到降序的大值列表，用于填充偶数索引
   • 较小值段：取排序数组剩下的前半段，本身为升序，用于填充奇数索引
3. 交替合并两个列表，优先放大值列表元素，再放小值列表元素，直到所有元素合并完成

修正后代码 #

def max_min_naive(lst):
    # 对原数组升序排序
    sorted_lst = sorted(lst)
    n = len(sorted_lst)
    # 拆分大小值段
    split_idx = n // 2
    small_lst = sorted_lst[:split_idx]
    big_lst = sorted_lst[split_idx:][::-1] # 大值段反转成降序
    
    big_ptr = 0
    small_ptr = 0
    res = []
    # 交替合并
    while big_ptr < len(big_lst) or small_ptr < len(small_lst):
        if big_ptr < len(big_lst):
            res.append(big_lst[big_ptr])
            big_ptr += 1
        if small_ptr < len(small_lst):
            res.append(small_lst[small_ptr])
            small_ptr += 1
    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))

运行后输出结果：

[5, 1, 4, 2, 3]
[7, 1, 6, 2, 5, 3, 4]

完全符合需求预期。

内容的提问来源于stack exchange，提问作者Jang