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


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

Претпоставимо да смо дали знак цео број поредак. Проблем „Бројање индексних парова са једнаким елементима у низу“ тражи да се утврди број пара индекса (и, ј) на такав начин да арр [и] = арр [ј] 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

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

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

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

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

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