Python中列表的包含范围

Question

我正在尝试找到列表部分中的最小元素。在以下示例中，a是开始，b是结束。我希望这些索引可以包含列表中的元素，因此如果列表是[1,2,3,9,4,10]，则索引1到4将包括2和4。

def minimum (a,b,list):
    return min(list[a:b])

换句话说，有没有办法使list[a:b]包含端点？

- Apollo

---

不幸的是，在Python中，列表切片并不是这样工作的。如果您想让b索引包含在内，只需将1添加到它即可... - MattDMo

另外，不要将变量命名为内置函数名称，例如list、dict、str等。 - MattDMo

Answer 1

默认情况下，不行。 对于这种情况，更为常规的做法是：

min(li[a:b + 1])

同时要注意不要将变量命名为list，因为这可能会导致意外后果（静默的命名空间问题），因为"list"也是内置的列表容器类型的名称。

如果您只想编写自己的最小方法，可以使用上述方法将此行为封装在您的最小方法中，以便您永远不必再考虑它。

顺便说一下：标准列表切片使用O(N)空间，并且如果多次调用minimum，则对于大型列表而言可能会变得昂贵。更便宜的O(1)空间替代方法是：

def minimum(a, b, li):
    min(itertools.islice(li, a, b + 1))

编辑：如果从列表开头开始切片或者内存限制很紧，才使用islice。它首先迭代到a，而不是直接索引到a，这可能需要O(b)的运行时间。

更好的解决方案是像这样做，其运行时间为O(b-a)，空间复杂度为O(1)：

def minimum(li, a=0, b=None):
    if b is None:
        b = len(li) - 1
    if b - a < 0:
        raise ValueError("minimum() arg is an empty sequence")
    current_min = li[a]
    for index in xrange(a, b + 1):
        current_min = min(current_min, li[index])

    return current_min

如果列表是静态的（在查询序列期间没有删除和插入元素），您可以使用更高级的解决方案，即使用区间树执行范围最小查询。 建立该树需要O(N)运行时间和O(N)空间，尽管此后的所有查询仅需要O(log(N))运行时间和额外的O(1)空间。有关详细信息，请访问http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/。

- Brian Schmitz