Python,基于x的拆分坐标列表

Question

我有一个坐标列表,我需要根据它们的x值将它们分成两半.像这样的东西:

l = [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (3, 1)]
left = []
right = []
for i in l:
    if i[0] < 2:
        left.append(i)
    else:
        right.append(i)

print(left)
print(right)

输出:

[(0, 0), (1, 0), (0, 1), (1, 1)]
[(2, 0), (3, 0), (2, 1), (3, 1)]

有更快的方法吗？

Answer 1

你在O(n)中做到了.如果您对列表进行了排序,则可以通过在二进制搜索中搜索pivot元素,在O(log(n))中进行排序.事先对自己进行排序只是为了使用二进制搜索不会得到回报,因为排序是O(n*log(n))

另一方面...... 它真的重要吗？如果这是你的瓶颈,那么可能会重新考虑整个算法或数据结构.例如,如果您有一个复杂的问题,您需要在某些区域操作点,您可以考虑使用kd-trees