C++程序 数组平衡点的程序

C++程序 数组平衡点的程序

编写一个函数 int equilibrium(int[] arr, int n) ,它会给定大小为n的序列arr[],返回一个平衡点的索引(如果存在),否则返回-1。数组的平衡点是这样一个索引,使得较低的索引处的元素的总和等于较高的索引处元素的总和。例如,在一个数组A中:

示例:

输入 : A[] = {-7, 1, 5, 2, -4, 3, 0}

输出 : 3

3是平衡点,因为:

A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

输入 : A[] = {1, 2, 3}

输出 : -1

方法1(简单但效率低)

使用两个循环。外部循环遍历所有元素,内部循环可以找出外部循环选择的当前索引是否是平衡点或者不是。

// C++ program to find equilibrium
// index of an array
#include <bits/stdc++.h>
using namespace std;

int equilibrium(int arr[], int n)
{
    int i, j;
    int leftsum, rightsum;

    /* Check for indexes one by one until
    an equilibrium index is found */
    for (i = 0; i < n; ++i)
    {    

        /* get left sum */
        leftsum = 0;
        for (j = 0; j < i; j++)
            leftsum += arr[j];

        /* get right sum */
        rightsum = 0;
        for (j = i + 1; j < n; j++)
            rightsum += arr[j];

        /* if leftsum and rightsum 
        are same, then we are done */
        if (leftsum == rightsum)
            return i;
    }

    /* return -1 if no equilibrium
    index is found */
    return -1;
}

// Driver code
int main()
{
    int arr[] = { -7, 1, 5, 2, -4, 3, 0 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << equilibrium(arr, arr_size);
    return 0;
}

// This code is contributed
// by Akanksha Rai(Abby_akku)

输出

3

时间复杂度: O(n^2)

辅助空间: O(1)

方法2(巧妙而高效)

首先获取整个数组的总和。然后遍历数组并保持初始化为零的左侧和。在循环中,可以通过逐个减去元素来得到右侧和。感谢Sambasiva提供了这个解决方案和代码。

1)初始化leftsum为0
2)将数组的总和作为sum
3)遍历数组,对于每个索引i,执行以下操作。
a) 更新sum以获得右部分和。
sum = sum- arr[i]
//现在sum是右部分和
b) 如果leftsum等于sum,则返回当前索引。
//更新leftsum以进行下一次迭代。
c) leftsum = leftsum + arr[i]
4)返回-1
// 如果没有找到平衡点则退出循环

下面是上述方法的实现:

这个图像展示了上述方法的详细运行过程:

C++程序 数组平衡点的程序

下面是上述方法的实现:

// C++找到数组的平衡索引程序
//包含bits/stdc ++。h
使用namespace std;
 
int equilibrium(int arr [],int n)
{
    int sum = 0; //初始化整个数组的总和
    int leftsum = 0; //初始化leftsum
 
    / *找到整个数组的总和* /
    for(int i = 0; i 



**输出**
```cpp
第一个平衡指数是3
</code></pre>

<strong>时间复杂度:</strong> O(n)<br />
<strong>辅助空间:</strong> O(1)

<strong>方法3:</strong>

这是一种非常简单和直接的方法。这个想法是两次取数组的前缀和。一次从数组的前端,另一次从数组的后端。

在进行两个前缀和后,运行循环并检查某个i是否来自某个数组的两个前缀和等于另一数组的前缀和,那么可以将该点视为平衡点。

<pre><code class="language-cpp  line-numbers">// C ++程序查找数组的平衡指数
# include
使用命名空间std;
 
int equilibrium(int a [],int n)
{
    if(n == 1)
        返回(0);
    int forward [n] = {0};
    int rev [n] = {0};
 
    //从前端数组中获取前缀和
    for(int i = 0; i  0; i--){
        if(i <= n-2){
            rev [i] = rev [i + 1] + a [i];
        }其他{
            rev [i] = a [i];
        }
    }
 
    //检查前缀和是否相等
    //总和
    for(int i = 0; i 



**输出**
```cpp
第一个平衡点位于索引3处

时间复杂度: O(N)

辅助空间: O(N)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例