Rayուցանիշի զույգերի քանակը զանգվածում հավասար տարրերով  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Atlassian Միջնաբերդ facebook Intuit Snapdeal քառակուսի Yandex
Դասավորություն Խանգարել Որոնում դասավորում

Ենթադրենք, մենք տվել ենք ամբողջ թիվ դասավորություն, «Rayուցանիշի զույգերի քանակը զանգվածում հավասար տարրերով» խնդիրը խնդրում է պարզել զույգ ցուցանիշների թիվը (ես, ժ) այնպես, որ arr [i] = arr [j] և i հավասար չէ j.

Օրինակ  

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

բացատրություն

Ինդեքսների զույգերն են. (0, 3), (1, 4), (2, 5)

Rayուցանիշի զույգերի քանակը զանգվածում հավասար տարրերովPin

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

բացատրություն

Ինդեքսների զույգերն են. (0, 1)

Ալգորիթմ  

  1. Հայտարարել ա Քարտեզ.
  2. Անցնել դասավորություն և յուրաքանչյուր տարրի հաճախականությունը հաշվեք և պահեք քարտեզի մեջ:
  3. Արդյունքը դրեք 0-ի վրա:
  4. Անցեք քարտեզը և քարտեզից ստացեք յուրաքանչյուր տարրի հաճախականությունը:
  5. Կատարեք ելք + = (VAL * (VAL - 1)) / 2, VAL- ը յուրաքանչյուր տարրի հաճախականությունն է:
  6. Վերադարձի արդյունքը:

բացատրություն

Մենք տվել ենք դասավորություն ամբողջ թվերի, մենք խնդրել ենք պարզել ընդհանուր ոչ: զանգվածում առկա զույգերն այնպես, որ նրանց ցուցանիշները նույնը չեն, բայց այդ ցուցանիշների տարրերը պետք է լինեն նույնը: Այսպիսով, մենք պատրաստվում ենք օգտագործել ա Հեշինգ դրա համար Կոճակումն ավելի լավ միջոց է, քան կոպիտ ուժի մեթոդը, որի դեպքում մենք պետք է այցելենք բոլոր այդ տարրերը `օգտագործելով լրացուցիչ ժամանակ Վրա2), Այսպիսով, մենք խուսափում ենք դրանից:

Մենք կհայտարարենք քարտեզ, վերցնելով յուրաքանչյուր տարր, հաշվելու և պահելու ենք յուրաքանչյուր տարրի հաճախականությունը քարտեզի վրա, եթե այն արդեն առկա է քարտեզում, տեղ պատրաստենք դրա համար, եթե այն արդեն առկա է, պարզապես ավելացնում է իր հաճախականությունը 1-ով:

Տես նաեւ,
Փոխանակեք հանգույցները զույգերով Leetcode Solutions

Համակցման բանաձև օգտագործելու համար մենք պետք է հաշվենք յուրաքանչյուր թվի հաճախականությունը: Մենք պատրաստվում ենք ընտրել մի քանի զույգ, որոնք բավարարում են հավասար տարրերի տվյալ պայմանը, բայց ոչ դրանց ցուցանիշները: Կարող ենք ենթադրել, որ զանգվածում առկա ցանկացած թիվ ցանկացած ցուցանիշում հայտնվում է k անգամ մինչև kth ինդեքսը: Դրանից հետո ընտրեք ցանկացած երկու ցուցանիշ ai եւy որը կհամարվի որպես 1 զույգ: Նմանապես, աy եւx կարող է լինել նաև զույգ: Այսպիսով, nC2 զույգերի քանակը պարզելու բանաձեւն է, որի համար arr [i] = arr [j] նույնպես հավասար է x- ի:

Rayանգվածի անցումից և յուրաքանչյուր տարրը և դրա առաջացումը քարտեզի վրա դնելուց հետո մենք կանցնենք քարտեզի վրա ՝ վերցնելով տարրի յուրաքանչյուր հաճախականությունը և դրա վրա կիրառելով բանաձև, ավելացնելով արդյունքը և պահելով այն արդյունքի մեջ: Մենք ստիպված ենք անընդհատ կրկնել այն, քանի դեռ չենք հատել բոլոր տարրերը և դրանց հաճախականությունները և գործողություն կատարել դրանց վրա: Եվ վերջապես, մենք կվերադարձնենք այդ արդյունքը:

C ++ կոդ ՝ զանգվածում հավասար տարրերով հավասար ցուցանիշների զույգերի քանակը գտնելու համար  

#include<iostream>
#include<unordered_map>

using namespace std;

int getNoOfPairs(int arr[], int n)
{
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
        MAP[arr[i]]++;

    int output = 0;
    for (auto it=MAP.begin(); it!=MAP.end(); it++)
    {
        int VAL = it->second;
        output += (VAL * (VAL - 1))/2;
    }
    return output;
}
int main()
{
    int arr[] = {2,3,1,2,3,1,4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getNoOfPairs(arr, n) << endl;
    return 0;
}
3

Java կոդ ՝ զանգվածում հավասար տարրերով հավասար ցուցանիշների զույգերի քանակը գտնելու համար  

import java.util.HashMap;
import java.util.Map;

class countIndexPair
{
    public static int getNoOfPairs(int arr[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<>();

        for(int i = 0; i < n; i++)
        {
            if(MAP.containsKey(arr[i]))
                MAP.put(arr[i],MAP.get(arr[i]) + 1);
            else
                MAP.put(arr[i], 1);
        }
        int output=0;
        for(Map.Entry<Integer,Integer> entry : MAP.entrySet())
        {
            int VAL = entry.getValue();
            output += (VAL * (VAL - 1)) / 2;
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,1,2,3,1,4};
        System.out.println(getNoOfPairs(arr,arr.length));
    }
}
3

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

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տես նաեւ,
Իտերատիվ նախնական պատվերի անցում

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

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: