减少时间复杂度:在列表中的元素之间求最小差异[关闭]

问题描述 投票:-2回答:3

我的目标是找到列表中任何两个元素之间的最小差异。我编写了以下代码,但我想知道在时间复杂度方面是否有更有效的方法。

    def minimumAbsoluteDifference(arr):
        arr.sort()
        min_diff = abs(arr[0] - arr[1])
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                if abs(arr[i] - arr[j]) < min_diff:
                    min_diff = abs(arr[i] - arr[j])
                else:
                    continue
        return min_dif
python arrays list
3个回答
2
投票

实际上,如果仔细看,您会发现对列表进行排序后不需要使用两个循环。您可以通过以下方式直接执行-

def minimumAbsoluteDifference(arr):
    arr.sort()
    min_diff = 10**10       #Initilising to an huge value
    for i in range(len(arr)-1):
        if arr[i+1] - arr[i] < min_diff: 
            min_diff = arr[i+1] - arr[i] 
    return min_dif

如何运作? -

  • 一旦对列表进行排序,最小绝对差的潜在候选者只是相邻元素

  • 一旦远离相邻元素,绝对差必然会增加

  • 例如,考虑排序列表为lst = [2,3,5,8,15]。我们开始比较2和3。一旦比较它们,就不必比较2和5,因为它们之间的差异将始终大于相邻元素。同样,我们只比较3 and 5,不比较3 and 8或其他任何带有3的元素。


因此,此修改后的解决方案将以O(nLogn)时间复杂度工作,这比使用2个循环O(n^2)更快。

希望这会有所帮助!


1
投票

一旦有了排序数组,就不需要扫描所有对:显然,元素i和元素i + 1之间的差异将小于或等于(i,i + 2)元素之间的差异。一种更快的方法是检查每两个相邻元素之间的差异:

def minimumAbsoluteDifference(arr):
   # assumption: there is more then one element in array
   arr.sort()
   min_diff = arr[1] - arr[0]
   for i in range(1, len(arr)):
      curr_diff = arr[i] - arr[i-1]
      min_diff = min(min_diff, curr_diff)
   return min_diff

遍历为O(n)的数组。每次此代码选择电流差和到目前为止找到的最小差之间的最小值。arr.sortO(nlogn),所以总时间复杂度为O(nlogn)。您的原始代码为必填项O(n^2)


1
投票

最简单的方法:

def minimumAbsoluteDifference(arr):
    arr.sort()
    min_diff = float('inf')                               # initiating with infinity value
    for i in range(2, len(arr)):                          # start from the second element
        min_diff = min(min_diff, abs(arr[i] - arr[i-1]))  # use the built-in minimum python method 
    return min_dif
© www.soinside.com 2019 - 2024. All rights reserved.