給出一個由 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)不可接受的程度。請幫忙了解哪種算法適合這個問題。
2 回答
慕萊塢森
TA貢獻1810條經驗 獲得超4個贊
以下方法可能有助于提高復雜性：
我首先會計算元素的累積和，即對于上面的示例，如下所示：
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;
}
藍山帝景
TA貢獻1843條經驗 獲得超7個贊
利用前綴和的概念可以降低時間復雜度。
使用 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)
添加回答
舉報
0/150
提交
取消