Leetcode шешімінің жақсы жұптарының саны


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Microsoft
Array Хэш математика

Проблемалық мәлімдеме

Бұл есепте бүтін сандар жиымы берілген және біз a [i] = a [j] болатын жақсы жұптардың (a [i], a [j]) жалпы санының санын анықтауымыз керек.

мысал

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

Түсіндіру: (4), (0,3), (0,4), (3,4) индекстерінде 2,5 жақсы жұп бар.

[1,1,1,1]
6

Түсіндіру: массивтегі әр жұп жақсы.

Тәсіл (қатал күш)

Берілген есепте біз екі циклды қолдана аламыз, біреуі [i] үшін, екіншісі [j] үшін. Бұл кірістірілген цикл біз (a [i], a [j]) жұбы үшін мүмкін болатын барлық комбинацияны қайталаймыз және [i] -дің [j] -ге тең екендігін немесе болмауын тексереміз.

Алгоритм:

1. Санау айнымалысын құрып, нөлге теңестіріңіз.
2. Ішкі циклды i = 0-ден i = n-1-ге [i] үшін сыртқы циклды және [j] үшін ішкі циклды j = i + 1-ден j = n-1-ге дейін жүргізіңіз.
3. Егер a [i] = a [j] болса, оның мәнін 1-ге көбейту арқылы санау үшін ағымдағы жұпты қосыңыз.
4. count айнымалысының мәнін қайтарыңыз.

Leetcode шешімінің жақсы жұптарының санын енгізу

C ++ бағдарламасы

#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

Java бағдарламасы

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

Leetcode шешімі бар жұптардың санының күрделілігін талдау

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

O (N ^ 2): Мұндағы N - берілген жиымның өлшемі. Екі циклды қолданып, элементтердің барлық комбинацияларын i және j индексінде тексерген кезде уақыттың күрделілігі O (N ^ 2) болады.

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

O (1): Біз қосымша жад қолданбаймыз.

 

Тәсіл (оңтайландырылған)

Пайдалану арқылы шешімді оңтайландыруға болады Хэш картасы. I * j рет жұптардың барлық тіркесімдерінде қайталау қолданылмайды. Біз тек тең элементтерді санауымыз керек.
Егер массивтегі белгілі бір элементтің саны болса, осы ұқсас элементтер жиынтығындағы кез-келген екі элементті таңдау тәсілдерінің жалпы санын есептей аламыз.
Ол үшін біз 1-ші элементтен қайталап, әр элементтің санын әр қадамда жаңарта аламыз.
Біз элементті тапқан сайын, санау картасы айнымалысының көмегімен осы элементке дейін қанша ұқсас элементтер болғанын тексереміз. Бұл барлық алдыңғы элементтермен жұптастыра алатындай етіп.
Бұл санақты нәтижеге қосамыз және ағымдағы элементтің санын +1-ге жаңартамыз (көбейтеміз).

Leetcode шешімінің жақсы жұптарының саны

Алгоритм:
1. Кілті элемент және мәні осы элементтің ағымдағы саны болатын бүтін және бүтін санның картасын жасаңыз.
2. i = 0 -ден n-1-ге дейінгі әр элемент үшін a for циклін іске қосыңыз.
3. Картаға салмас бұрын санақты (a [i]) тауып, бұл мәнді res-ге қосыңыз.
4. Енді a [i] санын count (a [i]) = count (a [i]) + 1 ретінде жаңартыңыз.
5. res мәнін қайтарыңыз.

Leetcode шешімінің жақсы жұптарының санын енгізу

C ++ бағдарламасы

#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

Java бағдарламасы

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

Leetcode шешімі бар жұптардың санының күрделілігін талдау

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

O (N): Hash Map көмегімен әр элементтің санын жаңарту бойынша тұрақты жұмыс жүргізіп жатқандықтан, уақыттың күрделілігі O (N) болады.

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

O (N) : Біз әрбір бірегей элементтердің санын сақтау үшін Hash Map картасын қолданамыз. Нашар жағдайда N әр түрлі элементтер болуы мүмкін.