Python：列表中元素之间的最大差异 [英] Python: Maximum difference between elements in a list

问题描述

如果当前元素右边的元素更大，我需要找到未排序列表中元素之间的最大差值。例如：

  myList = [2、3、8、0、7]。 
  

函数应计算如下：

  present元素=2。
为3> 2？是。那么3-2 = 1 
是8> 2？是。那么8-2 = 6 
是0> 2？否。转到下一个元素。 
是7> 2？是。然后7-2 = 5，依此类推
 
最后我的输出= 7 
  

我的第一个解决方案如下：

  def maxDiff（a）：
l = len（a）
 arr = [] 
对于范围（l-1）中的i：
对于范围j在（i + 1，l）中：
如果a [j]> a [i]：
 diff = a [j]-a [i] 
 arr.append（diff）
 return（max（arr））
 
  def maxDiff（a）：
l = len（a） 
 diffList = [] 
对于范围（l-1）中的i：
 newList = a [i + 1：] 
 max1 = max（newList）
差= max1-a [i] 
 diffList.append（difference）
 return（max（diffList））
  
我的问题是第二个解决方案正确吗？如果是，那是否是最佳选择？这两个功能的时间复杂度是多少？还有其他更最佳的解决方案吗？
解决方案
第二种解决方案仍然在每次迭代时重新计算前缀列表的最大值。 
 
 
 
我认为您的两个解决方案都是正确的，但是第二个解决方案仍然至少是二次O（n ^ 2），因为您正在for循环中执行线性时间运算（例如 max（））。因此，请回答您的问题：不，这可能不是最佳解决方案。
 
 
 
如果我正确理解了该问题，则可以使用动态编程。考虑以下代码：
  def maxDiff（a）：
 vmin = a [0] 
 dmax = 0对于范围（len（a））中的i为
：如果（a [i]< vmin）：
 vmin = a [i] 
 elif（a [ i]-vmin> dmax）：
 dmax = a [i]-vmin 
返回dmax 
  
在这里，我们只是跟踪到目前为止所遇到的最小值和最大差异，因此允许我们仅遍历列表一次，而无需存储任何其他列表或进行任何嵌套循环。因此，根据比较操作，此函数的运行时间应为线性O（n）。
 
I need to find the maximum difference between elements in an unsorted list if the element to the right of the present element is greater. For eg: 
myList = [2, 3, 8, 0, 7]. 
Function should calculate as follows:
present element = 2.
is 3 > 2? Yes. Then 3-2 = 1
is 8 > 2? Yes. Then 8-2 = 6
is 0 > 2? No. Go to the next element.
is 7 > 2? Yes. Then 7-2 = 5 and so on

Finally my output = 7
My first solution is as follows:
def maxDiff(a):
l = len(a)
arr = []
for i in range(l-1):
    for j in range(i+1, l):
        if a[j] > a[i]:
            diff = a[j] - a[i]
            arr.append(diff)
return (max(arr))
I was said that this is not an optimal solution. I came up with another solution which is as follows:
def maxDiff(a):
l = len(a)
diffList = []
for i in range(l-1):
    newList = a[i+1:]
    max1 = max(newList)
    difference = max1 - a[i]
    diffList.append(difference)
return (max(diffList))    
My question is is the second solution correct? If yes, then is it optimal? What is the time complexity of both these functions? Is there any other solution that is more optimal?
解决方案
Your second solution still recalculates the max value of the prefix list on every iteration, which you don't need to do.

I think both of your solutions are correct, but the second one is still at least quadratic O(n^2) since you are performing linear-time operations (such as max()) in your for loop. So to answer your question: No, it's likely not an optimal solution.

If I understood the problem correctly, it can be solved using dynamic programming. Consider the following code:
def maxDiff(a):
    vmin = a[0]
    dmax = 0
    for i in range(len(a)):
        if (a[i] < vmin):
            vmin = a[i]
        elif (a[i] - vmin > dmax):
            dmax = a[i] - vmin
    return dmax
Here we are simply keeping track of the smallest value encountered so far, and the largest difference, thus allowing us to iterate only once through the list without the need for storing any additional lists or doing any nested looping. The runtime of this should therefore be linear, O(n), in terms of comparison operations.

                        
这篇关于Python：列表中元素之间的最大差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！