1

我在算法方面遇到了一些问题（要找到最大值和最小值），而不是算法本身，而是实现，让我解释一下：

假设列表是n = [0,1,1,2,3,5,8,13,-1,99]；len(n) = 10 然后globalMin, globalMax = n[0], n[0]#从列表中跳过1次迭代

现在我要做的是按“对”进行比较，所以由于我已经使用了 n[0]，我开始比较 n[1] 和 n[2] 以找到这两个之间的最大值和最小值，然后将其与y 全局最小值，最大值，然后是 n[3] 和 n[4] 并将 nm 与我的全局值进行比较，然后是 n[5] 和 n[6] .. 直到我必须比较 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]

但是，如果我的最后一个元素只有一个（如上例所示），这将不起作用，因此，您可以猜到，如果 min 或 max 是我列表中的最后一个元素，它将被忽略。我一直在尝试用索引或列表切片来解决这个问题，但一点运气都没有，有什么建议吗？我必须以“Pythonic”的方式执行此操作，并确保在不使用导入的情况下使其尽可能简单和简短。我已经计算出基于下一张图片的算法的其余部分：图片

4

2 回答 2

3

您可以先检查列表的长度，如果它是奇数长度，那么您可以将最后一个元素附加到列表的末尾。追加是一种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
于 2013-03-08T01:08:35.083 回答
2

我认为这是最 Pythonic 的实现：

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()（itertools.izip_longest()在 2.x 中）对项目进行分组，并重复使用相同迭代器的列表。然后我们循环这个，它给我们成对的值。然后我们进行检查，如果该值是最后一个，我们将其分配为local_minand local_max，否则，我们比较两个值并根据需要进行分配。

然后我们比较（并可能更新）global_min和global_max。

于 2013-03-08T01:21:44.200 回答