给定一个n个正整数的数组。查找要添加到数组中某个索引的最小正元素，以便将其划分为两个相等和的连续子数组。输出要添加的最小元素及其位置。如果可能有多个位置，则返回至少一个。 例如：
null
输入：arr[]={10,1,2,3,4} 输出：0 说明： 这个数组已经可以被分成两个连续的子数组，即{10}和{1,2,3,4}等和。所以我们需要在任何位置加0。（最小位置为0） 输入：arr[]={5,4} 产出：1 说明： 我们需要将1和4相加，这样两个子数组是{5}，因此输出是1（最小元素和它要添加的位置）。
先决条件： 前缀和 方法1（简单）： 一种简单的方法是计算从（arr[0]到arr[i]）和（arr[i+1]到arr[n-1]）的元素之和，在每一步找到这两个和之间的差，最小的差将给出要添加的元素。 方法2（高效） ：仔细分析表明，我们可以使用前缀和后缀和的概念。计算这两个值，并找出prefixSum[i]（其中prefixSum[i]是到第i个位置的数组元素之和）和SufixSum[i+1]（其中SufixSum[i+1]是从第（i+1）个位置到最后一个位置的数组元素之和）之间的绝对差。 例如。
arr 10 1 2 3 4prefixSum 10 11 13 16 20suffixSum 20 10 9 7 4Absolute difference between suffixSum[i + 1] and prefixSum[i]10 - 10 = 0 // minimum11 - 9 = 113 - 7 = 616 - 4 = 12Thus, minimum element is 0, for position,if prefixSum[i] is greater than suffixSum[i + 1], then position is "i + 1".else it's is "i".
下面是上述方法的实现。
C++
// CPP Program to find the minimum element to // be added such that the array can be partitioned // into two contiguous subarrays with equal sums #include <bits/stdc++.h> using namespace std; // Structure to store the minimum element // and its position struct data { int element; int position; }; struct data findMinElement( int arr[], int n) { struct data result; // initialize prefix and suffix sum arrays with 0 int prefixSum[n] = { 0 }; int suffixSum[n] = { 0 }; prefixSum[0] = arr[0]; for ( int i = 1; i < n; i++) { // add current element to Sum prefixSum[i] = prefixSum[i - 1] + arr[i]; } suffixSum[n - 1] = arr[n - 1]; for ( int i = n - 2; i >= 0; i--) { // add current element to Sum suffixSum[i] = suffixSum[i + 1] + arr[i]; } // initialize the minimum element to be a large value int min = suffixSum[0]; int pos; for ( int i = 0; i < n - 1; i++) { // check for the minimum absolute difference // between current prefix sum and the next // suffix sum element if ( abs (suffixSum[i + 1] - prefixSum[i]) < min) { min = abs (suffixSum[i + 1] - prefixSum[i]); // if prefixsum has a greater value then position // is the next element, else it's the same element. if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1; else pos = i; } } // return the data in struct. result.element = min; result.position = pos; return result; } // Driver Code int main() { int arr[] = { 10, 1, 2, 3, 4 }; int n = sizeof (arr) / sizeof (arr[0]); struct data values; values = findMinElement(arr, n); cout << "Minimum element : " << values.element << endl << "Position : " << values.position; return 0; } |
JAVA
// Java Program to find the minimum element to // be added such that the array can be partitioned // into two contiguous subarrays with equal sums import java.util.*; class GFG { // Structure to store the minimum element // and its position static class data { int element; int position; }; static data findMinElement( int arr[], int n) { data result= new data(); // initialize prefix and suffix sum arrays with 0 int []prefixSum = new int [n]; int []suffixSum = new int [n]; prefixSum[ 0 ] = arr[ 0 ]; for ( int i = 1 ; i < n; i++) { // add current element to Sum prefixSum[i] = prefixSum[i - 1 ] + arr[i]; } suffixSum[n - 1 ] = arr[n - 1 ]; for ( int i = n - 2 ; i >= 0 ; i--) { // add current element to Sum suffixSum[i] = suffixSum[i + 1 ] + arr[i]; } // initialize the minimum element to be a large value int min = suffixSum[ 0 ]; int pos= 0 ; for ( int i = 0 ; i < n - 1 ; i++) { // check for the minimum absolute difference // between current prefix sum and the next // suffix sum element if (Math.abs(suffixSum[i + 1 ] - prefixSum[i]) < min) { min = Math.abs(suffixSum[i + 1 ] - prefixSum[i]); // if prefixsum has a greater value then position // is the next element, else it's the same element. if (suffixSum[i + 1 ] < prefixSum[i]) pos = i + 1 ; else pos = i; } } // return the data in struct. result.element = min; result.position = pos; return result; } // Driver Code public static void main(String[] args) { int arr[] = { 10 , 1 , 2 , 3 , 4 }; int n = arr.length; data values; values = findMinElement(arr, n); System.out.println( "Minimum element : " + values.element + "Position : " + values.position); } } // This code is contributed by Rajput-Ji |
Python3
# Python Program to find the minimum element to # be added such that the array can be partitioned # into two contiguous subarrays with equal sums # Class to store the minimum element # and its position class Data: def __init__( self ): self .element = - 1 self .position = - 1 def findMinElement(arr, n): result = Data() # initialize prefix and suffix sum arrays with 0 prefixSum = [ 0 ] * n suffixSum = [ 0 ] * n prefixSum[ 0 ] = arr[ 0 ] for i in range ( 1 , n): # add current element to Sum prefixSum[i] = prefixSum[i - 1 ] + arr[i] suffixSum[n - 1 ] = arr[n - 1 ] for i in range (n - 2 , - 1 , - 1 ): # add current element to Sum suffixSum[i] = suffixSum[i + 1 ] + arr[i] # initialize the minimum element to be a large value mini = suffixSum[ 0 ] pos = 0 for i in range (n - 1 ): # check for the minimum absolute difference # between current prefix sum and the next # suffix sum element if abs (suffixSum[i + 1 ] - prefixSum[i]) < mini: mini = abs (suffixSum[i + 1 ] - prefixSum[i]) # if prefixsum has a greater value then position # is the next element, else it's the same element. if suffixSum[i + 1 ] < prefixSum[i]: pos = i + 1 else : pos = i # return the data in class. result.element = mini result.position = pos return result # Driver Code if __name__ = = "__main__" : arr = [ 10 , 1 , 2 , 3 , 4 ] n = len (arr) values = Data() values = findMinElement(arr, n) print ( "Minimum element :" , values.element, "Position :" , values.position) # This code is contributed by # sanjeev2552 |
C#
// C# Program to find the minimum element // to be added such that the array can be // partitioned into two contiguous subarrays // with equal sums using System; class GFG { // Structure to store the minimum element // and its position public class data { public int element; public int position; }; static data findMinElement( int []arr, int n) { data result = new data(); // initialize prefix and suffix // sum arrays with 0 int []prefixSum = new int [n]; int []suffixSum = new int [n]; prefixSum[0] = arr[0]; for ( int i = 1; i < n; i++) { // add current element to Sum prefixSum[i] = prefixSum[i - 1] + arr[i]; } suffixSum[n - 1] = arr[n - 1]; for ( int i = n - 2; i >= 0; i--) { // add current element to Sum suffixSum[i] = suffixSum[i + 1] + arr[i]; } // initialize the minimum element // to be a large value int min = suffixSum[0]; int pos = 0; for ( int i = 0; i < n - 1; i++) { // check for the minimum absolute difference // between current prefix sum and the next // suffix sum element if (Math.Abs(suffixSum[i + 1] - prefixSum[i]) < min) { min = Math.Abs(suffixSum[i + 1] - prefixSum[i]); // if prefixsum has a greater value then position // is the next element, else it's the same element. if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1; else pos = i; } } // return the data in struct. result.element = min; result.position = pos; return result; } // Driver Code public static void Main(String[] args) { int []arr = { 10, 1, 2, 3, 4 }; int n = arr.Length; data values; values = findMinElement(arr, n); Console.WriteLine( "Minimum element : " + values.element + "Position : " + values.position); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript Program to find the minimum element to // be added such that the array can be partitioned // into two contiguous subarrays with equal sums // Structure to store the minimum element // and its position class data { constructor(element, position){ this .element = element; this .position = position; } }; function findMinElement(arr, n) { let result = new data(); // initialize prefix and suffix sum arrays with 0 let prefixSum = new Array(n); let suffixSum = new Array(n); prefixSum[0] = arr[0]; for (let i = 1; i < n; i++) { // add current element to Sum prefixSum[i] = prefixSum[i - 1] + arr[i]; } suffixSum[n - 1] = arr[n - 1]; for (let i = n - 2; i >= 0; i--) { // add current element to Sum suffixSum[i] = suffixSum[i + 1] + arr[i]; } // initialize the minimum element to be a large value let min = suffixSum[0]; let pos=0; for (let i = 0; i < n - 1; i++) { // check for the minimum absolute difference // between current prefix sum and the next // suffix sum element if (Math.abs(suffixSum[i + 1] - prefixSum[i]) < min) { min = Math.abs(suffixSum[i + 1] - prefixSum[i]); // if prefixsum has a greater value then position // is the next element, else it's the same element. if (suffixSum[i + 1] < prefixSum[i]) pos = i + 1; else pos = i; } } // return the data in struct. result.element = min; result.position = pos; return result; } // Driver Code let arr = [ 10, 1, 2, 3, 4 ]; let n = arr.length; let values; values = findMinElement(arr, n); document.write( "Minimum element : " + values.element + "<br>Position : " + values.position); // This code is contributed by _saurabh_jaiswal </script> |
输出：
Minimum element : 0Position : 0
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
