資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究用 C++ 在陣列中查詢一個元素，使得左陣列的和等於右陣列的和
假設我們有一個數組 A，其中包含 n 個元素。我們的任務是將陣列 A 分成兩個子陣列，使得每個子陣列的和相等。假設陣列 A = [2, 3, 4, 1, 4, 5]，輸出為 1，這樣就取了以 1 為界限分割的前後子陣列。即 [2, 3, 4] 和 [4, 5]。
要解決這個問題，我們要計算右和中除了第一個元素之外的整個陣列。考慮這是分割槽元素。我們將從左到右遍歷。從右和中減去一個元素，並將一個元素加到左和中，我們取其滿足右和 = 左和的那個點。
示例
#include<iostream>
using namespace std;
int getPartitionElement(int arr[], int size) {
int right = 0, left = 0;
for (int i = 1; i < size; i++)
right += arr[i];
for (int i = 0, j = 1; j < size; i++, j++) {
right -= arr[j];
left += arr[i];
if (left == right)
return arr[i + 1];
}
return -1;
}
int main() {
int arr[] = { 2, 3, 4, 1, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Partition element: " << getPartitionElement(arr, size);
}輸出
Partition element: 1
更新於：2019-10-29
656 次瀏覽
廣告