按降序合并两个已排序列表为一个列表

Question

我已经能够解决如何按升序合并两个已排序的列表了，但是我在找到一种在相反方向上合并这两个列表成一个降序列表的方法时遇到了困难。有没有办法不用在合并后再翻转字符串？

- John Wahlberg

---

如果将 > 改为 <= 会发生什么？ - Chai T. Rex

请确认：lst1和lst2都是按升序排序的，对吗？ - Hemerson Tacon

请记住，您需要使用相同的函数来完成递归，即也要使用“merge”函数而不是第二个函数“merge_recur”。 - Hemerson Tacon

“<=” 似乎不能用于将列表按照相反的顺序排序。是的，lst1 和 lst2 都按升序排序。我已经更新了代码，以便正确命名函数。 - John Wahlberg

Answer 1

你只需要反过来做所有的事情--从尾部检索项目而不是头部，进行比较时选择更大的那个，并在另一个用尽时以相反的顺序返回剩余的列表：

def merge(lst1, lst2):
    if not lst1:
        return lst2[::-1]
    if not lst2:
        return lst1[::-1]
    if lst1[-1] < lst2[-1]:
        return [lst2[-1]] + merge(lst1, lst2[:-1])
    else:
        return [lst1[-1]] + merge(lst1[:-1], lst2)

所以：

 merge([2,5,9,12], [0,1,3,4,8])

会返回：

 [12, 9, 8, 5, 4, 3, 2, 1, 0]

- blhsing

---

有没有不使用递归的方法来实现这个？ - John Wahlberg

你可以发布一个单独的问题，因为它与这里的问题性质非常不同。 - blhsing

谢谢帮助！还有没有不用使用 [::-1] 的方法来完成这个操作，因为那只是翻转字符串而已？ - John Wahlberg

不客气。如果您不想使用 [::-1]，您可以通过循环遍历列表并从尾部逐个迭代列表项，然后将该项附加到新列表中来自行反转列表。重要的是，您需要以相反的顺序返回剩余的列表，因为您希望输出按降序排列，但输入列表是按升序排列的。 - blhsing

你也可以使用内置的 reversed。 - jpp