来自 codility 的 Min Abs Sum 任务

Question

There is already a topic关于这个任务，但我想问一下我的具体做法。任务是：

Let A be a non-empty array consisting of N integers.

The abs sum of two for a pair of indices (P, Q) is the absolute value |A[P] + A[Q]|, for 0 ≤ P ≤ Q < N.

For example, the following array A:

A[0] = 1 A1 = 4 A[2] = -3 has pairs of indices (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2). The abs sum of two for the pair (0, 0) is A[0] + A[0] = |1 + 1| = 2. The abs sum of two for the pair (0, 1) is A[0] + A1 = |1 + 4| = 5. The abs sum of two for the pair (0, 2) is A[0] + A[2] = |1 + (−3)| = 2. The abs sum of two for the pair (1, 1) is A1 + A1 = |4 + 4| = 8. The abs sum of two for the pair (1, 2) is A1 + A[2] = |4 + (−3)| = 1. The abs sum of two for the pair (2, 2) is A[2] + A[2] = |(−3) + (−3)| = 6. Write a function:

def solution(A)

that, given a non-empty array A consisting of N integers, returns the minimal abs sum of two for any pair of indices in this array.

For example, given the following array A:

A[0] = 1 A1 = 4 A[2] = -3 the function should return 1, as explained above.

Given array A:

A[0] = -8 A1 = 4 A[2] = 5 A[3] =-10 A[4] = 3 the function should return |(−8) + 5| = 3.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

官方的解法是O(N*M^2)，但我觉得O(N)可以解。我的方法是先去掉重复项，然后对数组进行排序。然后我们检查两端并计算绝对总和，将两端向彼此移动。我们尝试移动左端、右端或两者。如果这不能改善结果，我们的总和是最低的。我的代码是：

def solution(A):
    A = list(set(A))
    n = len(A)
    A.sort()
    beg = 0
    end = n - 1
    min_sum = abs(A[beg] + A[end])
    while True:
        min_left = abs(A[beg+1] + A[end]) if beg+1 < n else float('inf')
        min_right = abs(A[beg] + A[end-1]) if end-1 >= 0 else float('inf')
        min_both = abs(A[beg+1] + A[end-1]) if beg+1 < n and end-1 >= 0 else float('inf')
        min_all = min([min_left, min_right, min_both])
        if min_sum <= min_all:
            return min_sum
        if min_left == min_all:
            beg += 1
            min_sum = min_left
        elif min_right == min_all:
            end -= 1
            min_sum = min_right
        else:
            beg += 1
            end -= 1
            min_sum = min_both

它通过了几乎所有的测试，但不是全部。是我的代码有问题还是方法不对？

编辑： 在 aka.nice 回答后，我能够修复代码。现在得分 100%。

def solution(A):
    A = list(set(A))
    n = len(A)
    A.sort()
    beg = 0
    end = n - 1
    min_sum = abs(A[beg] + A[end])
    while beg <= end:
        min_left = abs(A[beg+1] + A[end]) if beg+1 < n else float('inf')
        min_right = abs(A[beg] + A[end-1]) if end-1 >= 0 else float('inf')
        min_all = min(min_left, min_right)
        if min_all < min_sum:
            min_sum = min_all
        if min_left <= min_all: 
            beg += 1
        else:
            end -= 1

    return min_sum

Answer 1

以数组A为例

-11 -5 -2 5 6 8 12

并逐步执行你的算法，你会得到一个过早的 return:

beg=0
end=6
min_sum=1
min_left=7
min_right=3
min_both=3
min_all=3
return min_sum

虽然有更好的解 abs(5-5)=0.

提示：你应该检查A[beg]和A[end]的符号来决定是继续还是退出循环。如果两者都 >= 0，如果两者都 <= 0，否则怎么办？

请注意，A.sort() 有一个不可忽略的成本，很可能 O(N*log(N))，它将主导您展示的解决方案的成本。

顺便问一下，官方成本O(N*M^2)中的M是多少？

而你提供的link又是一道题（求和A的所有元素或它们的对立面）

来自 codility 的 Min Abs Sum 任务

Min Abs Sum task from codility

algorithm