查找数组中的绝对最小值

Question

给出一个由 N 个整数组成的非空数组 A。数组 A 代表磁带上的数字。任何整数 P，使得 0 < P < N，将该磁带分割成两个非空部分：A[0]、A[1]、...、A[P − 1] 和 A[P]、A[ P + 1]，...，A[N − 1]。两部分之间的差异是以下值：|(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|换句话说，它是第一部分之和与第二部分之和之间的绝对差。例如，考虑数组 A：A[0] = 3A[1] = 1A[2] = 2A[3] = 4A[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写一个函数：  class Solution { public int solution(int[] A); }给定一个包含 N 个整数的非空数组 A，返回可以实现的最小差异。例如，给定：A[0] = 3A[1] = 1A[2] = 2A[3] = 4A[4] = 3该函数应返回 1，如上所述。为以下假设编写一个有效的算法：N是[2..100,000]范围内的整数；数组 A 的每个元素都是 [−1,000..1,000] 范围内的整数。针对上述问题，我尝试了以下方法，    int firstSum = 0;    int secondSum = 0;    int tot = Integer.MAX_VALUE;    List<Integer> col = new ArrayList<>();    int k=0;    while(m<A.length)    {        firstSum = firstSum + A[k];         for(int i=m; i<A.length; i++)        {            secondSum = secondSum + A[i];        }        k++;    }    System.out.println("Min DIfference: " +tot);由于上面的工作正常，但其时间复杂度达到了O(N*N)不可接受的程度。请帮忙了解哪种算法适合这个问题。

Answer 1

以下方法可能有助于提高复杂性：

我首先会计算元素的累积和，即对于上面的示例，如下所示：

int[] A = {3,1,2,4,3};

for(int i = 1; i< A.length; i++){

    A[i] = A[i-1]+A[i];

}

生产：

[3, 4, 6, 10, 13]

[A.length-1]并在第二个循环中计算每个索引处的每个子和与总和的绝对差i

|A[i] - (A[A.length-1] + A[i])|

你的方法可能类似于：

public static int solution(int[] A){

    for(int i = 1; i< A.length; i++){

        A[i] = A[i-1]+A[i];

    }

    System.out.println(Arrays.toString(A));

    int min = Integer.MAX_VALUE;

    for(int i = 0; i< A.length-1; i++){

        if(Math.abs(A[i]-A[A.length-1]+A[i]) < min){

            min = Math.abs(A[i]-A[A.length-1]+A[i]);

        }

    }

    return min;

}

您还可以使用内置方法Arrays.parallelPrefix(int[] array, IntBinaryOperator op)来累积数组的元素并摆脱第一个循环。来自javadoc

使用提供的函数并行累积给定数组的每个元素。例如，如果数组最初包含 [2, 1, 0, 3] 并且操作执行加法，则返回时数组包含 [2, 3, 3, 6]。对于大型数组，并行前缀计算通常比顺序循环更有效。

代码使用Arrays.parallelPrefix

public static int solution(int[] A){

    Arrays.parallelPrefix(A, Integer::sum);        

    System.out.println(Arrays.toString(A));

    int min = Integer.MAX_VALUE;

    for(int i = 0; i< A.length-1; i++){

        if(Math.abs(A[i]-A[A.length-1]+A[i]) < min){

            min = Math.abs(A[i]-A[A.length-1]+A[i]);

        }

    }

    return min;

}

Answer 2

利用前缀和的概念可以降低时间复杂度。

使用 2 个前缀和数组：

1）forward_prefix_sum（从左到右数组元素的总和）

2）backward_prefix_sum（从右到左数组元素的总和）。

最后遍历数组计算差值最小。

answer = min(abs(forward_prefix_sum[i] - backward_prefix_sum[i]))对于 (0 <= i < n)

Time complexity: O(n)