Рубрики

Индекс равновесия массива

Индекс равновесия массива — это такой индекс, что сумма элементов при более низких индексах равна сумме элементов при более высоких индексах. Например, в массиве A:

Пример :

Input: A[] = {-7, 1, 5, 2, -4, 3, 0}
Output: 3
3 is an equilibrium index, because:
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

Input: A[] = {1, 2, 3}
Output: -1

Напишите функцию в равновесии (int [] arr, int n) ; при заданной последовательности arr [] размера n возвращает индекс равновесия (если есть) или -1, если индексов равновесия не существует.

Способ 1 (простой, но неэффективный)
Используйте две петли. Внешний цикл выполняет итерацию по всему элементу, и внутренний цикл определяет, является ли текущий индекс, выбранный внешним циклом, индексом равновесия или нет. Временная сложность этого решения составляет O (n ^ 2).

C ++

// C ++ программа для нахождения равновесия
// индекс массива
#include <bits/stdc++.h>

using namespace std;

  

int equilibrium(int arr[], int n)

{

    int i, j;

    int leftsum, rightsum;

  

    / * Проверять индексы по одному до

    найден индекс равновесия * /

    for (i = 0; i < n; ++i) 

    {     

  

        / * получить левую сумму * /

        leftsum = 0; 

        for (j = 0; j < i; j++)

            leftsum += arr[j];

  

        / * получить правильную сумму * /

        rightsum = 0; 

        for (j = i + 1; j < n; j++)

            rightsum += arr[j];

  

        / * если leftsum и rightsum

        то же самое, то мы сделали *

        if (leftsum == rightsum)

            return i;

    }

  

    / * вернуть -1, если нет равновесия

    индекс найден * /

    return -1;

}

  
// Код драйвера

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;

}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

С

// C программа для нахождения равновесия
// индекс массива

  
#include <stdio.h>

  

int equilibrium(int arr[], int n)

{

    int i, j;

    int leftsum, rightsum;

  

    / * Проверять индексы по одному до

      найден индекс равновесия * /

    for (i = 0; i < n; ++i) {       

  

        / * получить левую сумму * /

        leftsum = 0; 

        for (j = 0; j < i; j++)

            leftsum += arr[j];

  

        / * получить правильную сумму * /

        rightsum = 0; 

        for (j = i + 1; j < n; j++)

            rightsum += arr[j];

  

        / * если leftsum и rightsum совпадают,

           тогда мы сделали *

        if (leftsum == rightsum)

            return i;

    }

  

    / * вернуть -1, если индекс равновесия не найден * /

    return -1;

}

  
// Код драйвера

int main()

{

    int arr[] = { -7, 1, 5, 2, -4, 3, 0 };

    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("%d", equilibrium(arr, arr_size));

  

    getchar();

    return 0;

}

Джава

// Java-программа для нахождения равновесия
// индекс массива

  

class EquilibriumIndex {

    int equilibrium(int arr[], int n)

    {

        int i, j;

        int leftsum, rightsum;

  

        / * Проверять индексы по одному до

           найден индекс равновесия * /

        for (i = 0; i < n; ++i) {

  

            / * получить левую сумму * /

            leftsum = 0;  

            for (j = 0; j < i; j++)

                leftsum += arr[j];

  

            / * получить правильную сумму * /

            rightsum = 0;

            for (j = i + 1; j < n; j++)

                rightsum += arr[j];

  

            / * если leftsum и rightsum совпадают,

               тогда мы сделали *

            if (leftsum == rightsum)

                return i;

        }

  

        / * вернуть -1, если индекс равновесия не найден * /

        return -1;

    }

    // Код драйвера

    public static void main(String[] args)

    {

        EquilibriumIndex equi = new EquilibriumIndex();

        int arr[] = { -7, 1, 5, 2, -4, 3, 0 };

        int arr_size = arr.length;

        System.out.println(equi.equilibrium(arr, arr_size));

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python программа для нахождения равновесия
# индекс массива

  
# функция для нахождения индекса равновесия

def equilibrium(arr):

    leftsum = 0

    rightsum = 0

    n = len(arr)

  

    # Проверять индексы по одному

    # пока индекс равновесия не будет найден

    for i in range(n):

        leftsum = 0

        rightsum = 0

      

        # получить левую сумму

        for j in range(i):

            leftsum += arr[j]

          

        # получить правильную сумму

        for j in range(i + 1, n):

            rightsum += arr[j]

          

        # если leftsum и rightsum совпадают,

        # тогда мы закончили

        if leftsum == rightsum:

            return i

      

    # возврат -1, если индекс равновесия не найден

    return -1

              
# код водителя

arr = [-7, 1, 5, 2, -4, 3, 0]

print (equilibrium(arr))

  
# Этот код предоставлен Абхишеком Шарамой

C #

// C # программа для нахождения равновесия
// индекс массива

  

using System;

  

class GFG {

    static int equilibrium(int[] arr, int n)

    {

        int i, j;

        int leftsum, rightsum;

  

        / * Проверка индексов по одному

         один до равновесия

        индекс найден * /

        for (i = 0; i < n; ++i) {

  

            // инициализируем левую сумму

            // для текущего индекса i

            leftsum = 0;

  

            // инициализировать правильную сумму

            // для текущего индекса i

            rightsum = 0;

  

            / * получить левую сумму * /

            for (j = 0; j < i; j++)

                leftsum += arr[j];

  

            / * получить правильную сумму * /

            for (j = i + 1; j < n; j++)

                rightsum += arr[j];

  

            / * если leftsum и rightsum

             то же самое, тогда мы сделали *

            if (leftsum == rightsum)

                return i;

        }

  

        / * вернуть -1, если нет равновесия

         индекс найден * /

        return -1;

    }

  

    // код драйвера

    public static void Main()

    {

        int[] arr = { -7, 1, 5, 2, -4, 3, 0 };

        int arr_size = arr.Length;

  

        Console.Write(equilibrium(arr, arr_size));

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php 
// PHP программа для нахождения равновесия
// индекс массива

  

function equilibrium($arr, $n

    $i; $j

    $leftsum;

    $rightsum

  

    / * Проверять индексы по одному до

    найден индекс равновесия * /

    for ($i = 0; $i < $n; ++$i

    {     

  

        / * получить левую сумму * /

        $leftsum = 0; 

        for ($j = 0; $j < $i; $j++) 

            $leftsum += $arr[$j]; 

  

        / * получить правильную сумму * /

        $rightsum = 0; 

        for ($j = $i + 1; $j < $n; $j++) 

            $rightsum += $arr[$j]; 

  

        / * если leftsum и rightsum

        то же самое, то мы сделали *

        if ($leftsum == $rightsum

            return $i

    

  

    / * вернуть -1, если нет равновесия

       индекс найден * /

    return -1; 

  
// Код драйвера

$arr = array( -7, 1, 5, 2, -4, 3, 0 ); 

$arr_size = sizeof($arr); 

echo equilibrium($arr, $arr_size); 

  
// Этот код добавлен
// от akt_mit
?>



Сложность времени:
O (n ^ 2)

Метод 2 (хитрый и эффективный)
Идея состоит в том, чтобы сначала получить общую сумму массива. Затем выполните итерацию по массиву и продолжайте обновлять левую сумму, которая инициализируется как ноль. В цикле мы можем получить правильную сумму, вычитая элементы один за другим. Спасибо Sambasiva за предложение этого решения и предоставление кода для этого.

1) Initialize leftsum  as 0
2) Get the total sum of the array as sum
3) Iterate through the array and for each index i, do following.
    a)  Update sum to get the right sum.  
           sum = sum - arr[i] 
       // sum is now right sum
    b) If leftsum is equal to sum, then return current index. 
       // update leftsum for next iteration.
    c) leftsum = leftsum + arr[i]
4) return -1 
// If we come out of loop without returning then
// there is no equilibrium index

На рисунке ниже показан пробный прогон вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для нахождения равновесия
// индекс массива
#include <bits/stdc++.h>

using namespace std;

  

int equilibrium(int arr[], int n) 

    int sum = 0; // инициализируем сумму всего массива

    int leftsum = 0; // инициализация leftsum

  

    / * Найти сумму всего массива * /

    for (int i = 0; i < n; ++i) 

        sum += arr[i]; 

  

    for (int i = 0; i < n; ++i) 

    

        sum -= arr[i]; // сумма теперь правильная для индекса i

  

        if (leftsum == sum) 

            return i; 

  

        leftsum += arr[i]; 

    

  

    / * Если индекс равновесия не найден, вернуть 0 * /

    return -1; 

  
// Код драйвера

int main() 

    int arr[] = { -7, 1, 5, 2, -4, 3, 0 }; 

    int arr_size = sizeof(arr) / sizeof(arr[0]); 

    cout << "First equilibrium index is " << equilibrium(arr, arr_size); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для нахождения равновесия
// индекс массива

  
#include <stdio.h>

  

int equilibrium(int arr[], int n)

{

    int sum = 0; // инициализируем сумму всего массива

    int leftsum = 0; // инициализация leftsum

  

    / * Найти сумму всего массива * /

    for (int i = 0; i < n; ++i)

        sum += arr[i];

  

    for (int i = 0; i < n; ++i) {

        sum -= arr[i]; // сумма теперь правильная для индекса i

  

        if (leftsum == sum)

            return i;

  

        leftsum += arr[i];

    }

  

    / * Если индекс равновесия не найден, вернуть 0 * /

    return -1;

}

  
// Код драйвера

int main()

{

    int arr[] = { -7, 1, 5, 2, -4, 3, 0 };

    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("First equilibrium index is %d"

                 equilibrium(arr, arr_size));

  

    getchar();

    return 0;

}

Джава

// Java-программа для нахождения равновесия
// индекс массива

  

class EquilibriumIndex {

    int equilibrium(int arr[], int n)

    {

        int sum = 0; // инициализируем сумму всего массива

        int leftsum = 0; // инициализация leftsum

  

        / * Найти сумму всего массива * /

        for (int i = 0; i < n; ++i)

            sum += arr[i];

  

        for (int i = 0; i < n; ++i) {

            sum -= arr[i]; // сумма теперь правильная для индекса i

  

            if (leftsum == sum)

                return i;

  

            leftsum += arr[i];

        }

  

        / * Если индекс равновесия не найден, вернуть 0 * /

        return -1;

    }

  

   // Код драйвера

    public static void main(String[] args)

    {

        EquilibriumIndex equi = new EquilibriumIndex();

        int arr[] = { -7, 1, 5, 2, -4, 3, 0 };

        int arr_size = arr.length;

        System.out.println("First equilibrium index is "

                          equi.equilibrium(arr, arr_size));

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python программа для нахождения равновесия
# индекс массива

  
# функция для нахождения индекса равновесия

def equilibrium(arr):

  

    # найти сумму всего массива

    total_sum = sum(arr)

    leftsum = 0

    for i, num in enumerate(arr):

          

        # total_sum теперь верная сумма

        # для индекса i

        total_sum -= num

          

        if leftsum == total_sum:

            return i

        leftsum += num

       

      # Если индекс равновесия не найден,

      # затем вернуть -1

    return -1

      
# Код драйвера

arr = [-7, 1, 5, 2, -4, 3, 0]

print ('First equilibrium index is ',

       equilibrium(arr))

  
# Этот код предоставлен Абхишеком Шармой

C #

// C # программа для нахождения равновесия
// индекс массива

  

using System;

  

class GFG {

    static int equilibrium(int[] arr, int n)

    {

        // инициализируем сумму всего массива

        int sum = 0;

  

        // инициализация leftsum

        int leftsum = 0;

  

        / * Найти сумму всего массива * /

        for (int i = 0; i < n; ++i)

            sum += arr[i];

  

        for (int i = 0; i < n; ++i) {

  

            // сумма теперь правильная сумма

            // для индекса i

            sum -= arr[i];

  

            if (leftsum == sum)

                return i;

  

            leftsum += arr[i];

        }

  

        / * Если индекс равновесия не найден,

        затем верните 0 * /

        return -1;

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { -7, 1, 5, 2, -4, 3, 0 };

        int arr_size = arr.Length;

  

        Console.Write("First equilibrium index is " +

                           equilibrium(arr, arr_size));

    }

}
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для нахождения равновесия
// индекс массива

  

function equilibrium($arr, $n

    $sum = 0; // инициализировать сумму

              // весь массив

    $leftsum = 0; // инициализация leftsum

  

    / * Найти сумму всего массива * /

    for ($i = 0; $i < $n; ++$i

        $sum += $arr[$i]; 

  

    for ($i = 0; $i < $n; ++$i

    

        // сумма теперь правильная сумма

        // для индекса i

        $sum -= $arr[$i]; 

  

        if ($leftsum == $sum

            return $i

  

        $leftsum += $arr[$i]; 

    

  

    / * Если нет индекса равновесия

    найти, затем вернуть 0 * /

    return -1; 

  
// Код драйвера

$arr = array( -7, 1, 5, 2, -4, 3, 0 ); 

$arr_size = sizeof($arr); 

echo "First equilibrium index is "

      equilibrium($arr, $arr_size); 

  
// Этот код предоставлен ajit
?>

Выход:

First equilibrium index is 3

Сложность времени: O (n)

Как указал Самер, мы можем удалить оператор return и добавить оператор print для печати всех индексов равновесия вместо того, чтобы возвращать только один.

Пожалуйста, пишите комментарии, если вы обнаружите, что вышеприведенные коды / алгоритмы неверны, или найдете лучшие способы решения той же проблемы.

Рекомендуемые посты:

Индекс равновесия массива

0.00 (0%) 0 votes