നല്ല ജോഡികളുടെ എണ്ണം ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ മൈക്രോസോഫ്റ്റ്
അറേ ഹാഷിംഗ് മഠം

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ പൂർണ്ണസംഖ്യകളുടെ ഒരു നിര നൽകിയിരിക്കുന്നു, കൂടാതെ ഒരു നല്ല ജോഡികളുടെ എണ്ണം (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) ആയിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): ഞങ്ങൾ അധിക മെമ്മറിയൊന്നും ഉപയോഗിക്കുന്നില്ല.

 

സമീപനം (ഒപ്റ്റിമൈസ് ചെയ്തത്)

ഉപയോഗിച്ച് നമുക്ക് പരിഹാരം ഒപ്റ്റിമൈസ് ചെയ്യാൻ കഴിയും ഹാഷ് മാപ്പ്. I * j തവണ ജോഡികളുടെ എല്ലാ കോമ്പിനേഷനുകളിലും ആവർത്തനത്തിന്റെ ഉപയോഗമില്ല. നമുക്ക് തുല്യ ഘടകങ്ങൾ മാത്രം കണക്കാക്കണം.
അതായത്, അറേയിൽ ഒരു പ്രത്യേക ഘടകത്തിന്റെ എണ്ണം ഉണ്ടെങ്കിൽ, സമാന ഘടകങ്ങളുടെ ഈ കൂട്ടത്തിൽ ഏതെങ്കിലും രണ്ട് ഘടകങ്ങൾ തിരഞ്ഞെടുക്കുന്നതിനുള്ള ആകെ എണ്ണം കണക്കാക്കാം.
ഇതിനായി നമുക്ക് ചെയ്യാൻ കഴിയുന്നത്, നമുക്ക് ആദ്യ ഘടകത്തിൽ നിന്ന് ആവർത്തിക്കാനും ഓരോ ഘട്ടത്തിലും ഓരോ ഘടകത്തിന്റെയും എണ്ണം അപ്‌ഡേറ്റ് ചെയ്യാനും കഴിയും.
ഒരു മൂലകം കണ്ടെത്തുമ്പോഴെല്ലാം ഒരു കൗണ്ട് മാപ്പ് വേരിയബിൾ ഉപയോഗിച്ച് ഈ ഘടകത്തിന് മുമ്പായി എത്ര സമാന ഘടകങ്ങൾ നിലവിലുണ്ടെന്ന് ഞങ്ങൾ പരിശോധിക്കും. അതിനാൽ മുമ്പ് സംഭവിച്ച എല്ലാ ഘടകങ്ങളുമായി ജോടിയാക്കാൻ ഇതിന് കഴിയും.
ഞങ്ങളുടെ ഫലത്തിലേക്ക് ആ എണ്ണം ചേർത്ത് നിലവിലെ മൂലകത്തിന്റെ എണ്ണം +1 പ്രകാരം അപ്‌ഡേറ്റ് ചെയ്യുക (വർദ്ധിപ്പിക്കുക).

നല്ല ജോഡികളുടെ എണ്ണം ലീറ്റ്കോഡ് പരിഹാരം

അൽഗോരിതം:
1. മൂലകവും മൂല്യവും ആ മൂലകത്തിന്റെ നിലവിലെ എണ്ണത്തിന്റെ സംഖ്യയായ സംഖ്യയുടെയും സംഖ്യയുടെയും ഒരു ഹാസ് മാപ്പ് സൃഷ്ടിക്കുക.
2. i = 0 മുതൽ n-1 വരെയുള്ള ഓരോ ഘടകത്തിനും ഒരു ഫോർ ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക.
3. മാപ്പിൽ ഇടുന്നതിനുമുമ്പ് എണ്ണം (a [i]) കണ്ടെത്തി റെസിലേക്ക് ഈ മൂല്യം ചേർക്കുക.
4. ഇപ്പോൾ ഒരു [i] ന്റെ എണ്ണം എണ്ണമായി (a [i]) = എണ്ണം (a [i]) + 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

നല്ല ജോഡികളുടെ എണ്ണത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം ലീറ്റ്കോഡ് പരിഹാരം

സമയ സങ്കീർണ്ണത

O (N): ഹാഷ് മാപ്പ് ഉപയോഗിച്ച് ഓരോ മൂലകത്തിന്റെയും എണ്ണം അപ്‌ഡേറ്റ് ചെയ്യുന്നതിൽ ഞങ്ങൾ നിരന്തരമായ പ്രവർത്തനങ്ങൾ നടത്തുന്നതിനാൽ, സമയ സങ്കീർണ്ണത O (N) ആയിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (N) : ഓരോ അദ്വിതീയ ഘടകങ്ങളുടെയും എണ്ണം സംഭരിക്കാൻ ഞങ്ങൾ ഒരു ഹാഷ് മാപ്പ് ഉപയോഗിക്കുന്നു. ഏറ്റവും മോശം അവസ്ഥയിൽ N വ്യത്യസ്ത ഘടകങ്ങൾ ഉണ്ടാകാം.