Python：我正在尝试查找列表中两个元素之间的最大差异。

Question

我需要找出列表中任意两个元素之间的最大差值。在列表[1,2,3,4,5]中，使用for循环可以得到最大差值为4（在元素1和5之间）。

该程序需要输出这两个元素的位置（0和4）以及它们的值（1和5）。

我只能找出相邻值之间的最大差值，但如果最大值在其他位置开始，例如[4,1,6,3,10,8]，则会出现问题，其中最大差值在1和10之间（位置1和4）。有人能帮帮我吗？

- user3452835

---

抱歉，我忘了提到我必须使用for循环来完成这个任务。 - user3452835

考虑列表中距离最远的两个元素。它们与列表中的其他元素相比，还有什么“特别”的地方吗？ - Kyle Strand

请不要在评论中添加澄清说明；请编辑原始问题。 - Kyle Strand

Answer 1

您可以使用内置函数max和min分别找到最大值和最小值，然后使用列表方法index在列表中找到它们的索引。

numlist = [1, 2, 3, 4, 5]

max_val = max(numlist)
min_val = min(numlist)

max_pos = numlist.index(max_val)
min_pos = numlist.index(min_val)

- ajay

---

第2行和第3行应该是“numlist”，而不是“maxlist”。第4行和第5行也应该是“numlist”，而不仅仅是“list”。此外，您的答案非常完美地回答了这个问题，应该被接受为答案。 - manty

Answer 2

在朴素的方法中，你只需要两个嵌套循环来确保每个元素访问其他所有列表元素。由于你只需要检查每一对元素一次，所以每次内部循环开始的索引只需要从下一个位置开始即可：

lst = [1, 2, 3, 4, 5]

max_i, max_j = None, None # stores the indexes
max_d = -1 # stores the maximum distance we have seen so far

# iterate through all indexes of the list
for i in range(len(lst)):
    # iterate through all indexes, but starting from the index `i+1`
    for j in range(i + 1, len(lst)):
        d = abs(lst[i] - lst[j])
        if d > max_d:
            # memorize everything if the distance is larger than what we know
            max_i, max_j, max_d = i, j, abs(d)

print(max_i, max_j, max_d) # 0 4 4

如果需要将每个列表元素相互比较，则使用两个嵌套循环当然不是最有效的方法，但基本上这就是解决方案。对于您要查找最大距离的情况，正如其他人指出的那样，您只需要查看最大和最小的列表项，这两个项都可以在线性时间内确定。

---

如您在评论中所说，似乎只允许使用for循环，因此我们仍可以通过仅迭代一次来自行在线性时间内进行最小/最大值查找，从而使其更有效：

# set the current maximum and minimum to the first index
max_i, min_i = 0, 0

# iterate the list from the second index
for i in range(1, len(lst)):
    # check if we’re larger than the current maximum
    if lst[i] > lst[max_i]:
        max_i = i

    # check if we’re smaller than the current minimum
    if lst[i] < lst[min_i]:
        min_i = i

distance = lst[max_i] - lst[min_i]
print(min_i, max_i, distance) # 0 0 4

这基本上与mgilson的答案相同。我们只是自己完成内置函数max和min的工作，并手动找到最小值和最大值。

- poke

---

这非常有帮助！谢谢！ - user3452835

Answer 3

您可以首先对列表进行排序，然后获取最小值和最大值。同时，使用index()来获取元素的位置：

L = [1, 2, 3, 4, 5]

temp = sorted(L) # sorted list

min = temp[0]
max = temp[-1] # index -1 will give the last element

测试：

print "min", min, L.index(min)
print "max", max, L.index(max)
print "difference", max - min

输出：

min 1 0
max 5 4
difference 4

- Christian Tapia

---

调用sorted函数将这个问题从O(n)的常数内存问题转换为O(n log n)、O(n log n)内存问题。这是非常低效的。 - David Ehrmann

@DavidEhrmann 这是一个包含5个小数字的列表，使用的编程语言是Python。我认为效率在这里并不是非常重要。 :P - TessellatingHeckler

尽管时间复杂度的 O(n lg n) 界限是正确的，但空间复杂度最坏为 O(n)，对于许多算法来说，它的空间复杂度是 O(1)。 - chepner

@chepner 抱歉，空间复杂度是我的错误。O(n) 是正确的。 - David Ehrmann

@TessellatingHeckler，你正在走一条很滑的路，这会在你处理实际问题时带来很多意外。 - David Ehrmann

Answer 4

只需将最大值减去最小值即可。在Python中这很简单。一种很酷的方法是使用itemgetter。如果您枚举列表中的项目，但对列表的原始值执行min/max操作，则可以同时找到最小/最大索引和值。就像这样：

>>> import operator
>>> values = [1, 2, 3, 4, 5]
>>>
>>> min_index, min_value = min(enumerate(values), key=operator.itemgetter(1))
>>> min_index, min_value
0, 1
>>> max_index, max_value = max(enumerate(values), key=operator.itemgetter(1))
4, 5
>>> difference = max_value - min_value
>>> difference
4

- anon582847382

Answer 5

这可以通过使用 max 和 min + enumerate 来实现：

biggest_idx, biggest_value = max(enumerate(lst), key=lambda x: x[1])
smallest_idx, smallest_value = min(enumerate(lst), key=lambda x: x[1])

e.g.:

>>> lst =  [1,2,3,4,5] 
>>> biggest_idx, biggest_value = max(enumerate(lst), key=lambda x: x[1])
>>> smallest_idx, smallest_value = min(enumerate(lst), key=lambda x: x[1])
>>> print biggest_idx, biggest_value
4 5
>>> print smallest_idx, smallest_value
0 1

- mgilson

Answer 6

它可以非常简单，只需要使用一些基本的编程知识和技能。

numlist=[4,1,6,3,10,8]
print('min value index : ' , numlist.index(min(numlist)))
print('max value index : ' , numlist.index(max(numlist)))
print('Max Difference : ',max(numlist)-min(numlist))

- Sravan K Ghantasala

Answer 7

min_i = 0
max_i = 0
for i in xrange(len(alist)):
    if alist[i] < alist[min_i]:
        min_i = i
    if alist[i] > alist[max_i]:
        max_i = i
print "min=%d, max=%d" % (alist[min_i], alist[max_i])
print "min index=%d, max index=%d", (min_i, max_i)
print "difference=%d" % (alist[min_i] - alist[max_i])

- Broseph