如何比较列表中的元素

Question

我在实现一个算法（用来找最大值和最小值）时遇到了一些麻烦，不是算法本身的问题，而是怎么把它写出来的问题，让我来解释一下：

假设我的列表是 n = [0,1,1,2,3,5,8,13,-1,99]; len(n) = 10。然后我设置 globalMin, globalMax = n[0], n[0]，这样做是为了跳过列表中的一个元素。

接下来，我需要通过“成对比较”的方式来找最大值和最小值。因为我已经用过了 n[0]，所以我从 n[1] 和 n[2] 开始比较，找出这两个数中的最大值和最小值，然后再和我的全局最小值和最大值进行比较。接着是 n[3] 和 n[4]，再比较它们和我的全局值，依此类推，直到要比较 n[9] 和 n[10]。不过你可以看到，n[10] 在我的列表中并不存在。我原本想用列表切片来解决这个问题，代码如下：

 for i in range(1, len(n), 2):

    if n[i:i+1] > n[i+1:i+2]:
      minl, maxl = n[i+1:i+2], n[i:i+1] # minl = local min; maxl = local max
    else:
      maxl, minl = n[i+1:i+2], n[i:i+1]

但是如果我的最后一个元素只有一个（就像上面的例子），那么这个方法就不管用了。所以，正如你所猜的，如果最小值或最大值是列表中的最后一个元素，它就会被忽略。我一直在尝试用索引或列表切片来修复这个问题，但一直没有成功，有什么建议吗？我需要用一种“Pythonic”的方式来做，并确保尽量简单和简短，不使用任何导入。我已经想好了算法的其他部分，基于下面的图片： 图片

Answer 1

我认为这是最符合Python风格的实现方式：

from itertools import zip_longest

n = [0, 1, 1, 2, 3, 5, 8, 13, -1, 99]
global_min = global_max = n[0]

groups = [iter(n)] * 2
for a, b in zip_longest(*groups):
    if b is not None:
        if a > b:
            local_min, local_max = b, a
        else:
            local_min, local_max = a, b
    else:
        local_min = local_max = a
    if local_min < global_min:
        global_min = local_min
    if local_max > global_max:
        global_max = local_max

print(global_min, global_max)

我们通过使用 itertools.zip_longest()（在2.x版本中是itertools.izip_longest()）来对项目进行分组，并且重复使用同一个迭代器的列表。接着，我们遍历这些分组，这样就能得到成对的值。然后我们检查，如果这个值是最后一个，就把它赋值给 local_min 和 local_max，否则，我们就比较这两个值，并根据情况进行赋值。

接下来，我们比较（并可能更新） global_min 和 global_max。

Answer 2

你可以先检查一下列表的长度，如果长度是奇数，那就可以把最后一个元素加到列表的末尾。添加元素是一个O(1)的操作，所以这不会影响整体的时间复杂度。

你可以使用一个while循环：

In [78]: lis = [0,1,1,2,3,5,8,13,-1]

In [79]: if len(lis)%2 !=0 :  #if the list is of odd length then append the last item to it
    lis.append(lis[-1])
   ....:     

In [80]: i=0

In [81]: while i<len(lis)-1:
    if lis[i]>lis[i+1]:
        local_max,local_min=lis[i],lis[i+1]
    elif lis[i]<lis[i+1]:    
        local_max,local_min=lis[i+1],lis[i]
    else:
        local_max,local_min=lis[i],lis[i+1]
    print local_min,local_max
    i+=2
   ....:     
0 1
1 2
3 5
8 13
-1 -1

或者你可以使用一个迭代器：

In [86]: it=iter(lis)

In [87]: lis = [0,1,1,2,3,5,8,13,-1]

In [88]: if len(lis)%2 !=0 :
    lis.append(lis[-1])
   ....:     

In [89]: it=iter(lis)

In [90]: for _ in xrange(len(lis)/2):
   ....:     a,b=next(it),next(it)
   ....:     if a>b:
   ....:         local_max,local_min=a,b
   ....:     elif a<b:    
   ....:         local_max,local_min=b,a
   ....:     else:    
   ....:         local_max,local_min=a,b
   ....:     print local_min,local_max    
   ....:     
0 1
1 2
3 5
8 13
-1 -1