查找数组中的绝对最小值

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] = 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

写一个函数：

  class Solution { public int solution(int[] A); }

给定一个包含 N 个整数的非空数组 A，返回可以实现的最小差异。

例如，给定：

A[0] = 3

A[1] = 1

A[2] = 2

A[3] = 4

A[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++){&nbsp; &nbsp; 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){&nbsp; &nbsp; for(int i = 1; i< A.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; A[i] = A[i-1]+A[i];&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(Arrays.toString(A));&nbsp; &nbsp; int min = Integer.MAX_VALUE;&nbsp; &nbsp; for(int i = 0; i< A.length-1; i++){&nbsp; &nbsp; &nbsp; &nbsp; if(Math.abs(A[i]-A[A.length-1]+A[i]) < min){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = Math.abs(A[i]-A[A.length-1]+A[i]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return min;}您还可以使用内置方法Arrays.parallelPrefix(int[] array, IntBinaryOperator op)来累积数组的元素并摆脱第一个循环。来自javadoc使用提供的函数并行累积给定数组的每个元素。例如，如果数组最初包含 [2, 1, 0, 3] 并且操作执行加法，则返回时数组包含 [2, 3, 3, 6]。对于大型数组，并行前缀计算通常比顺序循环更有效。代码使用Arrays.parallelPrefixpublic static int solution(int[] A){&nbsp; &nbsp; Arrays.parallelPrefix(A, Integer::sum);&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; System.out.println(Arrays.toString(A));&nbsp; &nbsp; int min = Integer.MAX_VALUE;&nbsp; &nbsp; for(int i = 0; i< A.length-1; i++){&nbsp; &nbsp; &nbsp; &nbsp; if(Math.abs(A[i]-A[A.length-1]+A[i]) < min){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = Math.abs(A[i]-A[A.length-1]+A[i]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; 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)