Массивтегі элементтері бірдей индекс жұптарының саны  


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Atlassian Цитадель Facebook Intuit Шапшаң шаршы Яндекс
Array Hash іздеу Сұрыптау

Айталық, біз ан бүтін сан массив. «Массивтегі элементтері бірдей индекс жұптарын санау» мәселесі индекстер жұбының жоқтығын анықтайды (i, j) осылай arr [i] = arr [j] және i тең емес j.

мысал  

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

Түсіндіру

Индекстердің жұптары: (0, 3), (1, 4), (2, 5)

Массивтегі элементтері бірдей индекс жұптарының санытүйреуіш

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

Түсіндіру

Индекстердің жұптары: (0, 1)

Алгоритм  

  1. Декларация а карта.
  2. Көлденең жүріңіз массив және әрбір элементтің жиілігін санау және картаға сақтау.
  3. Шығарылымды 0 мәніне қойыңыз.
  4. Картаны айналып өтіп, әрбір элементтің жиілігін картадан алыңыз.
  5. Шығу + = (VAL * (VAL - 1)) / 2 жасаңыз, VAL - әр элементтің жиілігі.
  6. Шығуды қайтару.

Түсіндіру

Біз ан массив бүтін сандардан біз «жоқ» санын табуды сұрадық. массивте орналасқан жұптар, олардың индекстері бірдей емес, бірақ сол индекстердің элементтері бірдей болуы керек. Сондықтан біз а Хэш ол үшін. Хэштеу - бұл күш қолдану әдісіне қарағанда жақсы әдіс, онда біз қосымша элементтерді пайдаланып, барлық элементтерге баруымыз керек O (n2). Сондықтан біз бұған жол бермейміз.

Біз әр элементті ала отырып, картаны жариялаймыз, әр элементтің жиілігін санап, оны картаға сақтаймыз, егер ол картада болса, оған орын жасаймыз, егер ол қазірдің өзінде оның жиілігін 1-ге көбейтсе.

Сондай-ақ, қараңыз
Leetcode шешімдеріндегі түйіндерді ауыстыру

Аралас формуланы қолдану үшін әр санның жиілігін санауымыз керек. Біз тең элементтердің шарттарын қанағаттандыратын, бірақ олардың индекстерін емес бірнеше жұптарды таңдаймыз. Массивтегі кез-келген сан кез-келген индексте k-ші индекске дейін k рет пайда болады деп есептей аламыз. Содан кейін кез-келген екі индексті таңдаңыз ai жәнеy ол 1 жұп болып есептеледі. Сол сияқты, аy жәнеx жұп болуы да мүмкін. Сонымен, nC2 arr [i] = arr [j] х-ге тең болатын жұптардың санын анықтайтын формула.

Массивті кесіп өткеннен кейін және әрбір элементті және оның пайда болуын картаға енгізгеннен кейін, біз картаны айналып өтіп, элементтің әр жиілігін жинап, оған формула қолданамыз, нәтижеге қосамыз және оны шығарылымда сақтаймыз. Біз барлық элементтерді және олардың жиіліктерін айналып өтіп, оған операция жасағанға дейін қайталай беруіміз керек. Ақыр соңында, біз бұл өнімді қайтарамыз.

Массивтегі бірдей элементтері бар индекс жұптарының санын табуға арналған 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

Күрделілікті талдау  

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

Сондай-ақ, қараңыз
Итеративті алдын ала тапсырыс беру

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.