java - 查找数组中的绝对最小值

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)，这是 Not Acceptable 。 请帮忙了解哪种算法适合这个问题。

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

Cumulates, in parallel, each element of the given array in place, using the supplied function. For example if the array initially holds [2, 1, 0, 3] and the operation performs addition, then upon return the array holds [2, 3, 3, 6]. Parallel prefix computation is usually more efficient than sequential loops for large arrays.

使用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;
}