Бројање индексних парова са једнаким елементима у низу  


Ниво тешкоће Лако
Често питани у амазонка Атлассиан Цитадела фацебоок Интуит Снапдеал Квадрат иандек
Ред Хасх Претраживање сортирање

Претпоставимо да смо дали знак цео број поредак. Проблем „Бројање индексних парова са једнаким елементима у низу“ тражи да се утврди број пара индекса (и, ј) на такав начин да арр [и] = арр [ј] 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. Учините излаз + = (ВАЛ * (ВАЛ - 1)) / 2, ВАЛ је фреквенција сваког елемента.
  6. Повратни излаз.

Објашњење

Дали смо поредак целих бројева, тражили смо да сазнамо укупан бр. парова присутних у низу тако да њихови индекси нису исти, али би елементи на тим индексима требали бити исти. Па ћемо користити а Хасхинг за то. Хеширање је бољи начин од методе грубе силе у којем морамо да посетимо све те елементе користећи додатно време На2). Дакле, ми то избегавамо.

Прогласићемо карту, узимајући сваки елемент, бројати и чувати фреквенцију сваког елемента на мапи, ако је већ присутан на мапи, направити место за њу, ако већ постоји, само повећати њену учесталост за 1.

Види такође
Замените чворове у паровима Леетцоде решења

Да бисмо користили формулу комбинације, морамо да избројимо учесталост сваког броја. Изабраћемо неколико парова који задовољавају дати услов једнаких елемената, али не и њихове индексе. Можемо претпоставити да се било који број који је присутан у низу појављује к пута у било ком индексу до к-тог индекса. Затим одаберите било која два индекса аi и аy који ће се рачунати као 1 пар. Слично томе, аy и аx такође може бити пар. Тако, nC2 је формула за проналажење броја парова за које је арр [и] = арр [ј] такође једнако к.

Након преласка низа и стављања сваког елемента и његовог појављивања на мапу, прећи ћемо мапу, покупити сваку фреквенцију елемента и на њега применити формулу, сабирати излаз и складиштити га у излазу. Морамо то понављати док не пређемо све елементе и њихове фреквенције и не извршимо операцију на њему. И коначно, вратићемо тај излаз.

Ц ++ код за проналажење броја индексних парова са једнаким елементима у низу  

#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

Јава код за проналажење броја индексних парова са једнаким елементима у низу  

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

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

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

Он) где „Н“ је број елемената у низу.

Види такође
Итеративно превртање предбиљежбе

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

Он) где „Н“ је број елемената у низу.