चांगल्या जोडीची संख्या लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन मायक्रोसॉफ्ट
अरे हॅशिंग गणित

समस्या विधान

या समस्येमध्ये पूर्णांकांची एक अ‍ॅरे दिली गेली आहे आणि आम्हाला चांगल्या जोड्या (ए [i], ए [जे]) ची संख्या शोधून काढावी जिथे एक [i] = ए [जे] आहे.

उदाहरण

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

स्पष्टीकरणः निर्देशांकात (4), (0,3), (0,4), (3,4) येथे 2,5 चांगल्या जोड्या आहेत.

[1,1,1,1]
6

स्पष्टीकरणः अ‍ॅरेमधील प्रत्येक जोडी चांगली आहेत.

अ‍ॅप्रोच (ब्रूट फोर्स)

दिलेल्या समस्येमध्ये आपण दोन लूप वापरू शकतो, एक [i] आणि दुसरा जोडीच्या [जे] साठी. यामध्ये नेस्टेड लूप आम्ही जोडी (अ [i], ए [जे]) च्या सर्व संभाव्य संयोजनासाठी पुनरावृत्ती करू आणि [i] एक [जे] बरोबर आहे की नाही ते तपासू.

अल्गोरिदम:

1. एक काउंट व्हेरिएबल तयार करा आणि शून्यासह प्रारंभ करा.
२. नेस्टेड लूप, i = 2 ते i = n-0 साठी [i] साठी बाह्य पळवाट आणि j = i + 1 ते j = n-1 पर्यंत [j] साठी अंतर्गत लूप चालवा.
A. जर [i] = a [j] असेल तर, वर्तमान मूल्य जोडून त्याचे मूल्य १ ने वाढवून जोडा.
Count. काउंट व्हेरिएबलचे मूल्य परत करा.

चांगल्या जोडींच्या लेटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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): जेथे एन दिलेली अ‍ॅरेचा आकार आहे. जसे की आम्ही दोन लूप वापरत आहोत आणि अनुक्रमणिका i आणि j वर घटकांची सर्व जोडणी तपासत आहोत, वेळ जटिलता ओ (एन ^ 2) असेल.

स्पेस कॉम्प्लेक्सिटी 

ओ (1): आम्ही कोणतीही अतिरिक्त मेमरी वापरत नाही.

 

दृष्टीकोन (ऑप्टिमाइझ केलेले)

आम्ही सोल्यूशन वापरुन ऑप्टिमाइझ करू शकतो हॅश नकाशा. मी * जे वेळा जोडीच्या सर्व जोडण्यांवर पुनरावृत्ती करण्याचा काही उपयोग नाही. आपल्याला फक्त समान घटक मोजावे लागतील.
म्हणजे जर आपल्याकडे अ‍ॅरेमध्ये एखादी विशिष्ट घटकाची संख्या असेल तर समान घटकांच्या या सेटमध्ये कोणतेही दोन घटक निवडण्याच्या एकूण मार्गांची गणना करू शकतो.
त्यासाठी आपण काय करू शकतो ते म्हणजे, आम्ही पहिल्या घटकापासून पुनरावृत्ती करू शकतो आणि प्रत्येक घटकाची संख्या प्रत्येक चरणात अद्यतनित करू शकतो.
जेव्हा जेव्हा एखादा घटक आपल्याला आढळेल तेव्हा आम्ही गणना नकाशा व्हेरिएबल वापरुन या तत्त्वापूर्वी किती तत्सम तत्त्वे आधीपासून अस्तित्त्वात आली आहेत हे तपासू. जेणेकरून ते यापूर्वी आलेल्या सर्व घटकांसह जोडी बनवू शकेल.
आम्ही ती गणना आमच्या निकालात जोडू आणि वर्तमान घटांची गणना +1 करून अद्यतनित (वाढ) करू.

चांगल्या जोडीची संख्या लीटकोड सोल्यूशन

अल्गोरिदम:
१. पूर्णांक आणि पूर्णांकाचा नकाशा तयार करा ज्याची की घटक आहे आणि मूल्य त्या घटकाची वर्तमान गणना आहे.
२. i = 2 ते n-0 या प्रत्येक घटकासाठी लूपसाठी चालवा.
3. नकाशामध्ये ठेवण्यापूर्वी गणना (अ [i]) शोधा आणि हे मूल्य रेसमध्ये जोडा.
Now. आता a [i] ची गणना (a [i]) = गणना (a [i]) + १ म्हणून अद्यतनित करा.
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

चांगल्या जोड्यांच्या लेटकोड सोल्यूशनसाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन): जसे आपण हॅश मॅप वापरुन प्रत्येक घटकाची संख्या अद्ययावत करण्याचे निरंतर कार्य करत आहोत, त्यामुळे वेळ जटिलता ओ (एन) असेल.

स्पेस कॉम्प्लेक्सिटी 

ओ (एन) : आम्ही प्रत्येक अद्वितीय घटकांची संख्या संग्रहित करण्यासाठी हॅश नकाशा वापरत आहोत. सर्वात वाईट परिस्थितीत एन भिन्न घटक असू शकतात.