మంచి జతల సంఖ్య లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ మైక్రోసాఫ్ట్
అర్రే హ్యాషింగ్ మఠం

సమస్యల నివేదిక

ఈ సమస్యలో పూర్ణాంకాల శ్రేణి ఇవ్వబడుతుంది మరియు మొత్తం మంచి జతల సంఖ్యను మనం కనుగొనవలసి ఉంటుంది (a [i], a [j]) ఇక్కడ [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 = i + 1 నుండి j = n-1 వరకు [j] కోసం లోపలి లూప్‌ను అమలు చేయండి.
3. ఒక [i] = a [j] అయితే, దాని విలువను 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

మంచి జతల లీట్‌కోడ్ పరిష్కారం కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N ^ 2): ఇక్కడ N అనేది ఇచ్చిన శ్రేణి యొక్క పరిమాణం. మేము రెండు ఉచ్చులను ఉపయోగిస్తున్నప్పుడు మరియు సూచిక i మరియు j వద్ద అన్ని మూలకాల కలయికలను తనిఖీ చేస్తున్నప్పుడు, సమయ సంక్లిష్టత O (N ^ 2) అవుతుంది.

అంతరిక్ష సంక్లిష్టత 

ఓ (1): మేము అదనపు మెమరీని ఉపయోగించడం లేదు.

 

అప్రోచ్ (ఆప్టిమైజ్ చేయబడింది)

మేము ఉపయోగించడం ద్వారా పరిష్కారాన్ని ఆప్టిమైజ్ చేయవచ్చు హాష్ మ్యాప్. I * j సార్లు జతల యొక్క అన్ని కలయికలపై మళ్ళించడం యొక్క ఉపయోగం లేదు. మనం సమాన అంశాలను మాత్రమే లెక్కించాలి.
అనగా మనకు శ్రేణిలో ఒక నిర్దిష్ట మూలకం యొక్క లెక్క ఉంటే, ఈ సారూప్య మూలకాల సమితిలో ఏదైనా రెండు మూలకాలను ఎంచుకునే మొత్తం మార్గాలను లెక్కించవచ్చు.
దీని కోసం మనం చేయగలిగేది ఏమిటంటే, మేము 1 వ మూలకం నుండి మళ్ళి, ప్రతి దశలో ప్రతి మూలకం యొక్క గణనను నవీకరించవచ్చు.
మేము ఒక మూలకాన్ని కనుగొన్నప్పుడల్లా కౌంట్ మ్యాప్ వేరియబుల్ ఉపయోగించి ఈ మూలకానికి ముందు ఎన్ని సారూప్య అంశాలు ఉన్నాయో తనిఖీ చేస్తాము. తద్వారా ఇది మునుపటి సంభవించిన అన్ని అంశాలతో జత చేయవచ్చు.
మేము ఆ ఫలితాన్ని మా ఫలితానికి జోడించి, ప్రస్తుత మూలకం యొక్క గణనను +1 ద్వారా నవీకరిస్తాము (ఇంక్రిమెంట్).

మంచి జతల సంఖ్య లీట్‌కోడ్ పరిష్కారం

అల్గోరిథం:
1. పూర్ణాంకం మరియు పూర్ణాంకం యొక్క హస్ మ్యాప్‌ను సృష్టించండి, దీని కీ మూలకం మరియు విలువ ఆ మూలకం యొక్క ప్రస్తుత గణన.
2. i = 0 నుండి n-1 వరకు ప్రతి మూలకం రూపానికి a for loop ను అమలు చేయండి.
3. మ్యాప్‌లో పెట్టడానికి ముందు కౌంట్ (a [i]) ను కనుగొని, ఈ విలువను res కు జోడించండి.
4. ఇప్పుడు [i] యొక్క గణనను కౌంట్ (a [i]) = కౌంట్ (a [i]) + 1 గా నవీకరించండి.
5. res యొక్క విలువను తిరిగి ఇవ్వండి.

మంచి జతల లీట్‌కోడ్ పరిష్కారం కోసం అమలు

సి ++ ప్రోగ్రామ్

#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

మంచి జతల లీట్‌కోడ్ పరిష్కారం కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) : హాష్ మ్యాప్‌ను ఉపయోగించి ప్రతి మూలకం యొక్క గణనను నవీకరించడంలో మేము నిరంతరం పని చేస్తున్నందున, సమయ సంక్లిష్టత O (N) అవుతుంది.

అంతరిక్ష సంక్లిష్టత 

పై) : ప్రతి ప్రత్యేక అంశాల గణనను నిల్వ చేయడానికి మేము హాష్ మ్యాప్‌ను ఉపయోగిస్తున్నాము. చెత్త సందర్భంలో N వేర్వేరు అంశాలు ఉండవచ్చు.