F (a [i], a [j]) գումարը n ամբողջ թվերի զանգվածի բոլոր զույգերի վրա


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Cisco facebook Զբոսանք Publicis Sapient
Դասավորություն Խանգարել Մաթեմատիկա

Խնդրի հայտարարությունը խնդրում է պարզել 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 և checksum Ինչպես 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-ի: XNUMX և այդպես n ամբողջ թվերի զանգվածի բոլոր զույգերի վրա f (a [i], a [j]) գումար ենք գտնում:

Քննենք մի օրինակ.

Օրինակ

Arr [] = {1, 2, 3, 1, 3}, ելք ՝ 0, ստուգման գումար ՝ 0

  • Մենք կընտրենք 0-րդ ինդեքսի տարրը, այնուհետև կկատարենք, ապա բազմապատկելով դրա ինդեքսով և հանելով ստուգման գումարը և այնուհետև կավելացնենք արդյունքի մեջ

Արդյունք ՝ 0, ստուգման գումար ՝ 1

քարտեզ {1 = 1}, ցանկացած պայման չի բավարարում, ուստի մենք արժեքը ավելացնում ենք քարտեզի մեջ:

  • For 1st ինդեքսի տարր, կատարեք նույն գործողությունը, բայց այս անգամ այն ​​կբավարարի առաջին if հայտարարության պայմանը, և նորացված արդյունքը ստանալուց հետո կստանանք:

Թարմացված արդյունքը ՝ 0, ստուգման գումար ՝ 3

քարտեզ {1 = 1, 2 = 1}, և այս անգամ մենք այդ արժեքը ավելացնում ենք քարտեզի մեջ:

  • For 2nd էլեմենտ, նույն գործողությունը, ինչ նախկինում, այս անգամ այն ​​գտնում է a [i] -1 տարրը և մենք ստացանք թարմացված ելք.

Թարմացված արդյունքը ՝ 2, ստուգման գումար ՝ 6

քարտեզ {1 = 1, 2 = 1, 3 = 1} ՝ ավելացնելով տարրը և դրա հաճախականությունը:

  • 3-րդ տարրի համար այն բավարարում է if- ի երկրորդը, նշանակում է հետևում է, եթե քարտեզը պարունակում է a [i] +1 արժեք, ապա նորացված արդյունքը ստանալուց հետո.

Թարմացված ելք ՝ 0, ստուգման գումար ՝ 7, քարտեզ ՝ {1 = 2, 2 = 1, 3 = 1}

  • 4-րդ տարրի համար, եթե առաջին պնդումն անցնելուց հետո:

Թարմացված արդյունքը ՝ 4, ստուգման գումար ՝ 10

քարտեզ {1 = 2, 2 = 1, 3 = 2}

Եվ մենք կվերադարձնենք Արդյունքը. 4

Կոդ

C ++ կոդ `n ամբողջ թվերի զանգվածի բոլոր զույգերի վրա f (a [i], a [j]) գումար գտնելու համար

#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 կոդ ՝ n ամբողջ թվերի զանգվածի բոլոր զույգերի վրա f (a [i], a [j]) գումար գտնելու համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: HashMap- ի օգտագործումը մեզ թույլ է տալիս կատարել որոնում / ջնջում / ներմուծում Ո (1), Այսպիսով, n թվերի զանգվածի բոլոր զույգերի վրա f (a [i], a [j]) գումարը գտնելու ժամանակի բարդությունը վերածվում է գծայինի:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք կարող է HashMap- ում n ստեղներ տեղադրենք, այդպիսով տարածության բարդությունը գծային է: