හොඳ යුගල ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් මයික්රොසොෆ්ට්
අරා හැෂිං ගණිතය

ගැටළු ප්රකාශය

මෙම ගැටළුවේදී පූර්ණ සංඛ්‍යා සමූහයක් ලබා දී ඇති අතර, හොඳ යුගල ගණන (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] සඳහා i = 0 සිට i = n-1 දක්වා සහ අභ්‍යන්තර ලූපය [j] සඳහා j = i + 1 සිට j = n-1 දක්වා ධාවනය කරන්න.
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

හොඳ යුගල ලීට්කෝඩ් විසඳුම සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් ^ 2): මෙහි N යනු දී ඇති අරාවේ ප්‍රමාණයයි. අපි ලූප දෙකක් භාවිතා කරන අතර i සහ j දර්ශකයේ ඇති සියලුම මූලද්‍රව්‍ය සංයෝජනයන් පරීක්ෂා කරන විට, කාල සංකීර්ණතාව O (N ^ 2) වේ.

අභ්‍යවකාශ සංකීර්ණතාව 

ඕ (1): අපි කිසිදු අමතර මතකයක් භාවිතා නොකරමු.

 

ප්‍රවේශය (ප්‍රශස්ත)

භාවිතා කිරීමෙන් අපට විසඳුම ප්‍රශස්ත කළ හැකිය හැෂ් සිතියම. I * j වාර ගණනක යුගල සංයෝජනයන් හරහා නැවත යෙදීමෙහි කිසිදු ප්‍රයෝජනයක් නොමැත. අපට ගණනය කළ යුත්තේ සමාන මූලද්‍රව්‍ය පමණි.
එනම්, අරාවෙහි කිසියම් මූලද්‍රව්‍යයක් අපට තිබේ නම්, අපට සමාන මූලද්‍රව්‍ය සමූහයක ඕනෑම මූලද්‍රව්‍ය දෙකක් තෝරා ගැනීමේ සම්පූර්ණ ක්‍රම ගණන ගණනය කළ හැකිය.
මේ සඳහා අපට කළ හැකි දෙය නම්, අපට 1 වන මූලද්‍රව්‍යයෙන් නැවත යෙදිය හැකි අතර සෑම පියවරකදීම එක් එක් මූලද්‍රව්‍යයේ ගණන යාවත්කාලීන කළ හැකිය.
අපි මූලද්‍රව්‍යයක් සොයාගත් සෑම විටම ගණනය කිරීමේ සිතියම් විචල්‍යයක් භාවිතා කරමින් මෙම මූලද්‍රව්‍යයට පෙර සමාන මූලද්‍රව්‍ය කීයක් තිබේදැයි අපි පරීක්ෂා කරමු. එමඟින් කලින් සිදු වූ සියලුම මූලද්‍රව්‍ය සමඟ යුගලයක් සෑදිය හැකිය.
අපි එම අගය අපගේ ප්‍රති result ලයට එකතු කර +1 මගින් වත්මන් මූලද්‍රව්‍ය ගණන යාවත්කාලීන කරන්න (වැඩි කරන්න).

හොඳ යුගල ලීට්කෝඩ් විසඳුම

ඇල්ගොරිතම:
1. මූලද්‍රව්‍යය සහ අගය එම මූලද්‍රව්‍යයේ වත්මන් අගය වන පූර්ණ සංඛ්‍යා හා පූර්ණ සංඛ්‍යා සිතියම් සාදන්න.
2. i = 0 සිට n-1 දක්වා සෑම මූලද්‍රව්‍යයක් සඳහාම ලූපයක් ධාවනය කරන්න.
3. සිතියමට ඇතුළත් කිරීමට පෙර ගණනය (a [i]) සොයාගෙන මෙම අගය රෙස් එකට එක් කරන්න.
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 විවිධ අංග තිබිය හැකිය.