資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究JavaScript陣列平衡索引程式
陣列的平衡索引是指左側元素之和與右側元素之和相等的位置。換句話說，如果我們看一個大小為n的陣列，平衡索引i是一個點，使得：
arr[0] + arr[1] + ... + arr[i-1] = arr[i+1] + arr[i+2] + ... + arr[n-1]
其中i是平衡索引，arr是輸入陣列。我們也可以說，平衡索引i將陣列分成兩部分，使得左側元素的總和等於右側元素的總和。
例如：
讓我們考慮以下陣列：
A = [2, 4, -3, 0, -4, 6, 1] In this sequence, the equilibrium index is 3 (element 0) because (2+4-3) = (-4+6+1). It is also balanced with another equilibrium index 5 (element 6) because (2+4-3+0-4) = (1).
問題陳述
給定一個整數陣列，找到陣列的平衡點的索引。如果沒有平衡點，則返回-1。
示例
考慮一個整數陣列：
[3, 7, 1, 5, 10, 2, 7, 9]
這個陣列的平衡索引是4，因為索引之前的元素之和 (3+7+1+5 = 16) 等於索引之後的元素之和 (2+7+9 = 18)。
方法1：使用迴圈
使用兩個迴圈：外迴圈遍歷所有元素，內迴圈檢查外迴圈選擇的當前索引是否是平衡索引。這種方法的時間複雜度為O(n2)，稍後將解釋。使用兩個迴圈很簡單。目標是找到每個索引範圍的元素之和，並檢視是否存在平衡索引。外迴圈遍歷陣列，內迴圈檢查是否存在平衡索引。
演算法
使用兩個迴圈
外迴圈遍歷所有元素，內迴圈檢查外迴圈選擇的當前索引是否是平衡索引。
遍歷陣列
對於每個索引，找到當前索引左側和右側元素的和
如果left_sum和right_sum相等，則當前索引是平衡索引
否則，返回-1
此解決方案的時間複雜度為O(n2)
示例
<!DOCTYPE html>
<html>
<body>
<h3>Input Array: [-7, 1, 5, 2, -4, 3, 0]</h3>
<script>
// Input array
const arr = [-7, 1, 5, 2, -4, 3, 0];
// Flag to check if equilibrium index is found or not
let equilibriumIndexFound = false;
// Loop through each index i of the array
for (let i = 0; i < arr.length; i++) {
let leftSum = 0;
let rightSum = 0;
// Calculate the sum of elements to the left of i
for (let j = 0; j < i; j++) {
leftSum += arr[j];
}
// Calculate the sum of elements to the right of i
for (let j = i + 1; j < arr.length; j++) {
rightSum += arr[j];
}
// Check if the sum of elements to the left and right of i is equal
if (leftSum === rightSum) {
document.body.innerHTML += `The equilibrium index of the array is ${i}`;
equilibriumIndexFound = true;
break;
}
}
// Check if equilibrium index is not found
if (!equilibriumIndexFound) {
document.body.innerHTML += `There is no equilibrium index in the array`;
}
</script>
</body>
</html>
請記住，以上程式碼僅用於演示目的，不應在生產環境中使用，因為它沒有經過最佳化。它具有O(n2)的時間複雜度，對於大型陣列效率低下。
方法2：字首和
計算陣列平衡索引的另一種方法是字首和法。使用此方法，我們首先計算陣列的字首和，即從陣列開始到當前索引的元素之和。然後，使用字首和，我們遍歷陣列，檢查當前索引左側元素的總和是否等於當前位置右側元素的總和。
演算法
確定陣列的字首和。
遍歷陣列並使用字首和來檢視當前索引左側元素的和是否等於當前位置右側元素的和。
如果左側元素的和等於右側元素的和，則返回該索引作為平衡索引。
如果沒有平衡索引，則返回-1。
示例
<!DOCTYPE html>
<html>
<body>
<h3>Equilibrium Index</h3>
<script>
function equilibriumIndex(arr) {
let n = arr.length;
// Calculate the prefix sum of the array
let prefixSum = [];
prefixSum[0] = arr[0];
for (let i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
// Iterate through the array and check for equilibrium index
for (let i = 0; i < n; i++) {
let leftSum = (i == 0) ? 0 : prefixSum[i - 1];
let rightSum = prefixSum[n - 1] - prefixSum[i];
if (leftSum == rightSum) {
return i;
}
}
// No equilibrium index found
return -1;
}
let arr = [-7, 1, 5, 2, -4, 3, 0];
// Print the array
document.write("Array: " + arr + "<br>");
let result = equilibriumIndex(arr);
if (result == -1) {
document.write("No equilibrium index found");
} else {
document.write("Equilibrium index is " + result);
}
</script>
</body>
</html>
注意：查詢陣列平衡索引的字首和方法的時間複雜度為O(n)，其中n是陣列的大小
方法3：雙指標
在這種方法中，我們可以跟蹤兩個指標，一個在陣列的開頭，一個在陣列的結尾。使用這兩個指標，我們可以計算左右總和，並將指標相互移動，直到獲得平衡索引。
演算法
將leftSum初始化為0，並將右指標初始化為n-1。
從左到右遍歷陣列。
對於每個元素，將其新增到leftSum並從rightSum中減去它。
如果leftSum等於rightSum，則返回當前索引作為平衡索引。
如果沒有找到平衡索引，則返回-1。
示例
<!DOCTYPE html>
<html>
<body>
<h3>Equilibrium index of an array - Two Pointers Approach</h3>
<p id="input"></p>
<p id="output"></p>
<script>
const arr = [-7, 1, 5, 2, -4, 3, 0];
const n = arr.length;
let leftSum = 0;
let rightSum = 0;
document.getElementById("input").innerHTML = "Input Array: " + arr.join(", ");
for (let i = 0; i < n; i++) {
rightSum += arr[i];
}
for (let i = 0; i < n; i++) {
rightSum -= arr[i];
if (leftSum === rightSum) {
document.getElementById("output").innerHTML = "Equilibrium index: " + i;
break;
}
leftSum += arr[i];
}
if (document.getElementById("output").innerHTML === "") {
document.getElementById("output").innerHTML = "No equilibrium index found";
}
</script>
</body>
</html>
注意：查詢陣列平衡索引的字首和方法的時間複雜度為O(n)，其中n是陣列的大小。
結論
在本博文中，我們討論了透過各種方法查詢陣列的平衡索引。其中一些方法包括使用迴圈、字首和和雙指標方法。希望您覺得這些資訊有用。
423 次瀏覽
