Сума от f (a [i], a [j]) за всички двойки в масив от n цели числа


Ниво на трудност Лесно
Често задавани в Cisco Facebook Екскурзия Publicis Sapient
Array Хашиш Математически

Изложението на проблема изисква да се намери сумата от f (a [i], a [j]) за всички двойки в масив от n цели числа по такъв начин, че 1 <= i <j <= n, като се има предвид, че сме предоставени масив от цели числа.

Сума от f (a [i], a [j]) за всички двойки в масив от n цели числа

Пример

arr[] = {1, 2, 3, 1, 3}
4

Обяснение

Сдвоявайте само 3,1 и 3,1 двойки.

arr[]={2, 2, 1, 1, 3}
4

Обяснение

Тук също има две двойки (1, 3).

алгоритъм

  1. Декларирайте а карта и задайте продукция до 0 и контролна да 0.
  2. Преминете масива, започвайки от i = 0 да се i = n,
    1. Направете изход + = (i * a [i]) - контролна сума и контролна сума + = a [i];
    2. Проверете дали [i] -1 присъства като ключ на картата.
      1. Ако е вярно, актуализирайте изхода, като добавите стойността на [i] -1 на картата в изхода.
      2. Проверете дали [i] +1 присъства като ключ на картата. Ако е вярно, актуализирайте изхода, като добавите стойността на [i] +1 на картата в изхода.
    3. Ако нито едно от условията не удовлетворява, просто пребройте и съхранете честотата на елемента на масива в картата.
  3. Връщане на изхода.

Обяснение

Имаме масив цяло число, нашата задача е да открием сумата на всички двойки, присъстващи в масив, който отговаря на горното условие. Ако никоя от двойките не отговаря на даденото условие, тогава просто връщаме 0. За да разрешим това, ще използваме a Карта и едновременно извършване на всички операции върху всеки елемент от масив и актуализиране на изхода и проверка на нашата карта. Ще вземем допълнителна променлива, която следи за реалния ни изход, можем да го наречем като контролна сума. Ще зададем изхода и контролната сума на 0. И по този начин намираме сума от f (a [i], a [j]) за всички двойки в масив от n цели числа.

Нека разгледаме един пример:

Пример

Arr [] = {1, 2, 3, 1, 3}, изход: 0, контролна сума: 0

  • Ще изберем 0-ия индексен елемент и след това ще умножим по неговия индекс и ще извадим контролната сума и след това ще добавим това в изхода, имаме

Изход: 0, контролна сума: 1

map {1 = 1}, всяко условие не отговаря, така че добавяме стойността в картата.

  • За 1st index елемент, направете същата операция, но този път той ще удовлетвори условието на първия оператор if и след получаване на актуализирания изход получаваме.

Актуализиран изход: 0, контролна сума: 3

map {1 = 1, 2 = 1}, този път също добавяме тази стойност с нейното появяване в картата.

  • За 2nd елемент, извършена същата операция както преди, този път той намира елемента a [i] -1 и получихме актуализиран изход:

Актуализиран изход: 2, контролна сума: 6

map {1 = 1, 2 = 1, 3 = 1}, събирайки елемента и неговата честота.

  • За 3-ти елемент той удовлетворява втория оператор if, означава, че следва, ако картата съдържа стойността a [i] +1, след като получихме актуализирания изход:

Актуализиран изход: 0, контролна сума: 7, карта: {1 = 2, 2 = 1, 3 = 1}

  • За четвъртия елемент, след предаване на първия оператор if.

Актуализиран изход: 4, контролна сума: 10

карта {1 = 2, 2 = 1, 3 = 2}

И ще върнем изхода: 4

код

C ++ код за намиране на сума от f (a [i], a [j]) за всички двойки в масив от n цели числа

#include<iostream>
#include<unordered_map>

using namespace std;

int sum(int a[], int n)
{
    unordered_map<int, int> count;

    int output = 0, checksum = 0;
    for (int i = 0; i < n; i++)
    {
        output += (i * a[i]) - checksum;
        checksum += a[i];

        if (count[a[i] - 1])
            output -= count[a[i] - 1];

        if (count[a[i] + 1])
            output += count[a[i] + 1];

        count[a[i]]++;
    }
    return output;
}
int main()
{
    int a[] = { 1, 2, 3, 1, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << sum(a, n);
    return 0;
}
4

Java код за намиране на сума от f (a [i], a [j]) за всички двойки в масив от n цели числа

import java.util.HashMap;
public class pairSum
{
    public static int sum(int a[], int n)
    {
        HashMap<Integer,Integer> count = new HashMap<Integer,Integer>();

        int output = 0, checksum = 0;
        for (int i = 0; i < n; i++)
        {
            output += (i * a[i]) - checksum;
            checksum += a[i];

            if (count.containsKey(a[i] - 1))
                output -= count.get(a[i] - 1);

            if (count.containsKey(a[i] + 1))
                output += count.get(a[i] + 1);

            if(count.containsKey(a[i]))
            {
                count.put(a[i], count.get(a[i]) + 1);
            }
            else
            {
                count.put(a[i], 1);
            }
        }
        return output;
    }
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3, 1, 3 };
        int n = a.length;
        System.out.println(sum(a, n));
    }
}
4

Анализ на сложността

Сложност във времето

О (п) където "н" е броят на елементите в масива. Използването на HashMap ни позволява да извършим търсене / изтриване / вмъкване в O (1). По този начин сложността във времето за намиране на сумата от f (a [i], a [j]) по всички двойки в масив от n цели числа е намалена до линейна.

Сложност на пространството

О (п) където "н" е броят на елементите в масива. Тъй като може да се наложи да вмъкнем n ключове в HashMap, по този начин сложността на пространството е линейна.