Yaxşı cütlüklərin sayı Leetcode həll

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon microsoft
alqoritmlər Geyim kodlaşdırma Hashing müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions RiyaziyyatBaxılıb 43

Problem bəyanat

Bu məsələdə bir sıra ədədi verilmişdir və a [i] = a [j] olduğu yaxşı cütlərin ümumi sayının (a [i], a [j]) sayını tapmalıyıq.

misal

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

İzahat: (4), (0,3), (0,4), (3,4) indekslərində 2,5 yaxşı cüt var.

[1,1,1,1]
6

İzahat: Dizidəki hər cüt yaxşıdır.

Yanaşma (Brute Force)

Verilən məsələdə, bir cütün [i] üçün, ikincisi bir [j] üçün iki döngədən istifadə edə bilərik. Bu iç içə döngə (a [i], a [j]) cütlüyü üçün mümkün olan bütün birləşmə üçün təkrarlayacağıq və a [i] nin a [j] -ə bərabər olub olmadığını yoxlayacağıq.

Alqoritm:

1. Bir say dəyişəni yaradın və sıfır ilə başlayın.
2. I = 0-dan i = n-1-ə qədər bir [i] üçün xarici döngə və j = i + 1-dən j = n-1-ə qədər bir [j] üçün daxili döngə işlədin.
3. a [i] = a [j] olarsa, dəyərini 1 artıraraq saymaq üçün cari cüt əlavə edin.
4. Sayı dəyişəninin dəyərini qaytarın.

Yaxşı Cütlüyün Leetcode Çözümünün Tətbiqi

C ++ Proqramı

#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 Proqramı

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

Yaxşı Cütlüyün Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N ^ 2): Harada N, verilən massivin ölçüsüdür. İki döngədən istifadə etdiyimiz və i və j indeksindəki elementlərin bütün birləşmələrini yoxladığımız üçün zaman mürəkkəbliyi O (N ^ 2) olacaqdır.

Kosmik Mürəkkəblik 

O (1): Əlavə yaddaş istifadə etmirik.

 

Yanaşma (optimallaşdırılmış)

İstifadə edərək həlli optimallaşdırmaq olar Hash xəritəsi. Bütün cüt kombinasiyalar üzərində i * j dəfə təkrarlamaqdan heç bir istifadə yoxdur. Yalnız bərabər elementləri saymalıyıq.
yəni massivdə müəyyən bir elementin sayı varsa bu oxşar elementlər qrupundakı hər hansı iki elementi toplama yollarının ümumi sayını hesablaya bilərik.
Bunun üçün edə biləcəyimiz şey 1-ci elementdən təkrarlaya və hər addımda hər elementin sayını yeniləyə bilərik.
Nə vaxt bir element tapsaq, bir sayma xəritəsi dəyişənindən istifadə edərək bu elementdən əvvəl neçə oxşar elementin mövcud olduğunu yoxlayacağıq. Bütün əvvəlki meydana gələn elementlərlə cütləşə bilməsi üçün.
Bu sayımı nəticəmizə əlavə edəcəyik və cari elementin sayını +1 ilə yeniləyəcəyik (artırırıq).

Yaxşı cütlüklərin sayı Leetcode həll

Alqoritm:
1. Düyməsi element olan və dəyəri bu elementin cari sayı olan bir Tam və Tamsayı Has xəritəsi yaradın.
2. Hər bir forma for i = 0 - n-1 for a for loop çalıştırın.
3. Xəritəyə qoymadan əvvəl sayını (a [i]) tapın və bu dəyəri res-ə əlavə edin.
4. İndi a [i] sayını count (a [i]) = count (a [i]) + 1 kimi yeniləyin.
5. Res dəyərini qaytarın.

Yaxşı Cütlüyün Leetcode Çözümünün Tətbiqi

C ++ Proqramı

#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 Proqramı

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

Yaxşı Cütlüyün Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N): Hash Map istifadə edərək hər bir elementin sayını yeniləmək üçün davamlı iş apardığımız üçün zaman mürəkkəbliyi O (N) olacaqdır.

Kosmik Mürəkkəblik 

O (N) : Hər bir unikal elementin sayını saxlamaq üçün Hash Map istifadə edirik. Ən pis vəziyyətdə N fərqli element ola bilər.

Şərh yaz

Translate »
1