将排序列表拆分为两个列表

Question

我正在尝试将排序的整数列表拆分为两个列表。第一个列表将包含 n 下的所有整数，第二个列表将包含 n 上的所有整数。请注意，n 不必位于要拆分的列表中。

我可以轻松做到这一点：

under = []
over  = []
for x in sorted_list:
    if x < n:
        under.append(x)
    else
        over.append(x)

但知道列表已排序，似乎应该可以以更优雅的方式执行此操作。来自 itertools 的 takewhile 和 dropwhile 听起来像是解决方案，但我会在列表上迭代两次。

在功能上，我能做的最好的是：

i = 0
while sorted_list[i] < n:
    i += 1

under = sorted_list[:i]
over = sorted_list[i:]

但我什至不确定它是否真的比只遍历列表两次更好，而且它绝对不是更优雅。

我想我正在寻找一种方法来通过 takewhile 获取列表 return 和其余列表，也许是成对的。

Answer 1

我会使用以下方法，在其中找到索引并使用切片创建 under 和 over:

sorted_list = [1,2,4,5,6,7,8]
n=6

idx = sorted_list.index(n)
under = sorted_list[:idx]
over = sorted_list[idx:]

print(under)
print(over)

输出（与您的代码相同）：

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

编辑：据我了解这里的问题是一个找到最近索引的适应解决方案：

import numpy as np

sorted_list = [1,2,4,5,6,7,8]
n=3

idx = np.searchsorted(sorted_list, n)
under = sorted_list[:idx]
over = sorted_list[idx:]

print(under)
print(over)

输出：

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

Answer 2

这里的正确解是the bisect module。使用 bisect.bisect 找到 n 右侧的索引（或者如果它丢失将插入的索引），然后围绕该点切片：

 import bisect # At top of file

 split_idx = bisect.bisect(sorted_list, n)
 under = sorted_list[:split_idx]
 over = sorted_list[split_idx:]

虽然任何解决方案都将是 O(n)（毕竟您必须复制元素），但比较通常比简单的指针复制（以及相关的引用计数更新）更昂贵，并且 bisect 将排序 list 上的比较工作减少到 O(log n)，因此这通常（在较大的输入上）胜过简单地逐个元素地迭代和复制，直到找到拆分点。

如果你想让n结束，请使用bisect.bisect_left（找到n最左边的索引）而不是bisect.bisect（相当于bisect.bisect_right）在 over 而不是 under.

将排序列表拆分为两个列表

Split sorted list into two lists

python

split

list

sortedlist