Број решења добрих парова са Леетцоде-ом


Ниво тешкоће Лако
Често питани у амазонка мицрософт
Ред Хасхинг Математика

Изјава о проблему

У овом проблему дат је низ целих бројева и морамо да сазнамо број укупног броја добрих парова (а [и], а [ј]) где је а [и] = а [ј].

Пример

nums = [1,2,3,1,1,3]
4

Објашњење: Постоје 4 добра пара у индексима (0,3), (0,4), (3,4), (2,5).

[1,1,1,1]
6

Објашњење: Сваки пар у низу је добар.

Приступ (груба сила)

У датом задатку можемо користити две петље, једну за [и] и другу за [ј] пара. У ово угнежђена петља ми ћемо поновити све могуће комбинације за пар (а [и], а [ј]) и проверити да ли је а [и] једнак а [ј] или не.

Алгоритам:

1. Направите променљиву бројања и иницијализујте нулом.
2. Покрените угнежђену петљу, спољну петљу за а [и] од и = 0 до и = н-1 и унутрашњу петљу за а [ј] од ј = и + 1 до ј = н-1.
3. Ако је а [и] = а [ј], додајте тренутни пар за бројање повећавањем његове вредности за 1.
4. Врати вредност променљиве цоунт.

Примена за број добрих парова Леетцоде решења

Програм Ц ++

#include <bits/stdc++.h>
using namespace std;

int numIdenticalPairs(vector<int>& nums) 
{
       int res = 0;
       for(int i=0;i<nums.size();i++)
           for(int j=i+1;j<nums.size();j++)
               if(nums[i]==nums[j]) res++;
               
       return res;
}

int main() 
{
    vector<int> nums={1,2,3,1,1,3};
  
  cout<<numIdenticalPairs(nums)<<endl;

  return 0; 
}
4

Јава Програм

import java.lang.*;

class GoodPairs
{  
    public static int numIdenticalPairs(int[] nums) 
    {
        int res = 0;
        for(int i=0;i<nums.length;i++)
          for(int j=i+1;j<nums.length;j++)
             if(nums[i]==nums[j])   res++;

        return res;
    }

    public static void main(String args[])
    {
       int nums[]={1,2,3,1,1,3};
  
       System.out.println( numIdenticalPairs(nums));
        
    }
}
4

Анализа сложености броја решења добрих парова са Леетцоде-ом

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

О (Н ^ 2): Где је Н величина датог низа. Како користимо две петље и проверавамо све комбинације елемената на индексима и и ј, временска сложеност ће бити О (Н ^ 2).

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

О (1): Не користимо никакву додатну меморију.

 

Приступ (оптимизован)

Решење можемо оптимизирати помоћу Хасх Мап. Нема користи од понављања свих комбинација парова и * ј пута. Морамо рачунати само једнаке елементе.
тј. Ако имамо број одређеног елемента у низу, можемо израчунати укупан број начина бирања било која два елемента у овом скупу сличних елемената.
За ово што можемо учинити је да можемо извршити итерацију из првог елемента и ажурирати број сваког елемента у сваком кораку.
Кад год пронађемо елемент, проверићемо колико је сличних елемената већ било пре овог елемента помоћу променљиве мапе бројања. Тако да се може повезати са свим оним претходним елементима.
Додаћемо то бројање нашем резултату и ажурирати (увећати) број тренутног елемента за +1.

Број решења добрих парова са Леетцоде-ом

Алгоритам:
1. Направите Хас Мап од целог и целог броја чији је кључ елемент, а вредност тренутни број тог елемента.
2. Покрените фор петљу за сваки елемент облика и = 0 до н-1.
3. Пронађите број (а [и]) пре него што га ставите на мапу и додајте ову вредност у рес.
4. Сада ажурирајте број а [и] као цоунт (а [и]) = цоунт (а [и]) + 1.
5. Врати вредност рез.

Примена за број добрих парова Леетцоде решења

Програм Ц ++

#include <bits/stdc++.h>
using namespace std;

int numIdenticalPairs(vector<int>& nums) 
{
    int res = 0;
    unordered_map<int, int> count;
    for (int a: nums) 
    {
        res += count[a]++;
    }
  
    return res;
}

int main() 
{
    vector<int> nums={1,2,3,1,1,3};
  
  cout<<numIdenticalPairs(nums)<<endl;

  return 0; 
}
4

Јава Програм

import java.lang.*;
import java.util.*;

class GoodPairs
{  
    public static int numIdenticalPairs(int[] nums) 
    {
        int res = 0;
        Map<Integer,Integer> count= new HashMap<Integer,Integer>();
        for (int a: nums)
        {
            int cur=count.getOrDefault(a,0);
            res += cur;
            count.put(a,cur+1);
        }
        return res;
    }

    public static void main(String args[])
    {
       int nums[]={1,2,3,1,1,3};
  
       System.out.println( numIdenticalPairs(nums));
        
    }
}
4

Анализа сложености броја решења добрих парова са Леетцоде-ом

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

НА) : Како непрестано радимо на ажурирању броја сваког елемента користећи Хасх Мап, стога ће временска сложеност бити О (Н).

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

НА) : Користимо Хасх Мап за складиштење броја свих јединствених елемената. У најгорем случају може бити Н различитих елемената.