資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中將陣列平均分割所需的最小正整數
問題陳述
給定一個包含 N 個正整數的陣列，任務是找到可以放置在陣列任意兩個元素之間的最小正整數，使得在它之前出現的子陣列的元素之和等於在它之後出現的子陣列的元素之和，並且新放置的整數包含在兩個子陣列中的任意一個。
示例
如果 arr = {3, 2, 1, 5, 7, 10}，則輸出為 6。如果我們在 5 和 7 之間放置值 6，則左右子陣列的和將如下所示相等：
+ 2 + 1 + 5 + 6 = 17
7 + 10 = 17
演算法
- 設整個陣列的和為 S
- 思路是找到直到索引 i（包括 i）的左側和。設此和為 L
- 現在，子陣列 arri+1 .. N 的和為 S – L。設此和為 R
- 由於這兩個子陣列的和應該相等，因此上述獲得的兩個和 L 和 R 中較大的一個，應該減少到這兩個和中較小的值的程度，而較大值和較小值之間的差值，將是所需的正整數的值。
示例
#include <iostream>
#include <numeric>
#include <climits>
using namespace std;
int getMinimumSplitPoint(int *arr, int n) {
int sum = 0;
sum = accumulate(arr, arr + n, sum);
int leftSum = 0;
int rightSum = 0;
int minValue = INT_MAX;
for (int i = 0; i < n - 1; ++i) {
leftSum += arr[i]; rightSum = sum - leftSum;
if (leftSum > rightSum) {
int e = leftSum - rightSum;
if (e < minValue) {
minValue = e;
}
} else {
int e = rightSum - leftSum;
if (e < minValue) {
minValue = e;
}
}
}
return minValue;
}
int main() {
int arr[] = {3, 2, 1, 5, 7, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int minValue = getMinimumSplitPoint(arr, n);
cout << "Element " << minValue << " needs to be inserted\n";
return 0;
}輸出
編譯並執行上述程式時，它會生成以下輸出：
Element 6 needs to be inserted
更新於： 2019年11月22日
163 次檢視
廣告