python中的最小子数组差异 [英] Minimum subarray difference in python

问题描述

考虑一下，我有一个非空的整数数组: A0..An .并考虑参数 P其中0<P< = n .我需要找到由P拆分的左右子数组之间的最小绝对差.例如:

Consider I have a non-empty array of integers: A0..An. And consider a parameter P where 0 < P <=n. I need to find a minimum absolute difference between left and right subarray splited by P. For example:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

P = 1, difference = |3 − 10| = 7 
P = 2, difference = |4 − 9| = 5 
P = 3, difference = |6 − 7| = 1 
P = 4, difference = |10 − 3| = 7

在这种情况下，解决方案是 1

The solution in this case is 1

我完成了以下代码:

def solution(A):
    lsum, rsum = A[0], sum(A[1:])
    diff = abs(rsum - lsum)
    p = 1
    while True:
        lsum += A[p]
        rsum -= A[p]
        next = abs(rsum - lsum)
        if next < diff:
            diff = next
            p += 1
        else:
            return diff

但是我的解决方案存在一些错误.在某些情况下它可以工作，但在某些情况下会返回错误的答案.例如:在类似大序列，数字从-1到1，长度=〜100,000 的情况下，它将返回错误的答案

but I my solution has some bugs. It works in some cases but return wrong answer in some conditions. For example: in condition like large sequence, numbers from -1 to 1, length = ~100,000 it returns the wrong answer

P.S .:我完成了以下解决方案:

P.S.: I finished with solution below:

 def solution(lst):
    lsum, rsum = lst[0], sum(lst[1:])
    diff = abs(lsum - rsum)
    for i in xrange(1, len(lst) - 1):
        lsum += lst[i]
        rsum -= lst[i]
        ndiff = abs(lsum - rsum)
        diff = min(diff, ndiff)
    return diff

推荐答案

错误是这样的:

if next < diff:
    diff = next
    p += 1
else:
    return diff

如果 next 在 diff 上没有改善，则终止.这是错误的，因为稍后您仍可能会找到更好的解决方案.

You terminate if next is not improving on diff. This is wrong, since you still might find a better solution later on.

除此之外，我认为您的想法朝着正确的方向发展.解决错误的方法是无条件遍历整个数组，最后只返回 diff .像这样:

Other than that, I think your idea goes in the right direction. What you should do to fix your bug is go through the whole array unconditionally and just return diffin the end. Like so:

def solution(A):
    lsum, rsum = A[0], sum(A[1:])
    diff = abs(rsum - lsum)
    p = 1
    while p < (len(A)-1):
        lsum += A[p]
        rsum -= A[p]
        next = abs(rsum - lsum)
        if next < diff:
            diff = next
        p += 1
    return diff

(注意:我尝试进行尽可能少的修改，即尽可能地接近您的代码.而且，我并未对此进行真正的测试.但我希望您能理解.)

(Note: I tried to modify as little as possible, i.e. to stay as close to your code as possible. Also, I did not really test this. But I hope you get the idea.)

这篇关于python中的最小子数组差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！