የጥሩ ጥንዶች Leetcode መፍትሄ ብዛት


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን የ Microsoft
ሰልፍ ሃምሽንግ ሒሳብ

የችግሩ መግለጫ

በዚህ ችግር ውስጥ ብዙ ቁጥር ያላቸው ቁጥሮች ተሰጥተው የጠቅላላውን የጥንድ ጥንዶች ብዛት (ሀ [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. የቁጥር ተለዋዋጭ እሴት ይመልሱ።

ለጥሩ ጥንዶች ቁጥር Leetcode መፍትሄ አተገባበር

C ++ ፕሮግራም

#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

ለጥሩ ጥንዶች Leetcode መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N ^ 2) N የተሰጠው ድርድር መጠን የት ነው? ሁለት ቀለበቶችን እየተጠቀምን እና በመረጃ ጠቋሚ i እና j ላይ ሁሉንም የንጥሎች ጥምረት ስለምንፈተሽ ፣ የጊዜ ውስብስብነቱ O (N ^ 2) ይሆናል ፡፡

የቦታ ውስብስብነት 

ኦ (1) እኛ ማንኛውንም ተጨማሪ ማህደረ ትውስታ እየተጠቀምን አይደለም ፡፡

 

አቀራረብ (የተመቻቸ)

መፍትሄውን በመጠቀም ማመቻቸት እንችላለን የሃሽ ካርታ. በሁሉም የጥንድ i * j ጊዜያት ጥንድ ላይ ኢታቴር ማድረግ ምንም ጥቅም የለውም ፡፡ እኩል ክፍሎችን ብቻ መቁጠር አለብን ፡፡
ማለትም በምድቡ ውስጥ አንድ የተወሰነ ንጥረ ነገር ካለን በዚህ ተመሳሳይ ተመሳሳይ ንጥረ ነገሮች ውስጥ ማንኛውንም ሁለት አካላት የመምረጥ አጠቃላይ መንገዶችን ማስላት እንችላለን።
ለዚህ እኛ ማድረግ የምንችለው ከ 1 ኛ ንጥረ ነገር በመለየት የእያንዳንዱን ንጥረ ነገር ቆጠራ በእያንዳንዱ ደረጃ ማዘመን እንችላለን ፡፡
አንድ ንጥረ ነገር ባገኘን ቁጥር የቆጠራ ካርታ ተለዋዋጭን በመጠቀም ከዚህ ንጥረ ነገር በፊት ምን ያህል ተመሳሳይ አካላት እንደነበሩ እናጣራለን ፡፡ ከእነዚያ ሁሉ ቀደም ከተከሰቱ አካላት ጋር ጥንድ ማድረግ እንዲችል።
ያንን ቆጠራ በእኛ ውጤት ላይ እንጨምራለን እና የአሁኑን ንጥረ ነገር ብዛት በ +1 እናዘምነዋለን (ጭማሪ)።

የጥሩ ጥንዶች Leetcode መፍትሄ ብዛት

ስልተ-ቀመር
1. ቁልፉ ንጥረ ነገሩ እና እሴቱ የዚያ ንጥረ-ነገር የአሁኑ ቆጠራ የሆነ ሃስ ኢንደመር እና ኢንቲጀር ካርታ ይፍጠሩ።
2. ለእያንዳንዱ ንጥረ ነገር ቅፅ i = 0 እስከ n-1 አንድ ለ loop ያሂዱ ፡፡
3. ቆጠራውን (a [i]) ወደ ካርታው ውስጥ ከማስገባትዎ በፊት ይፈልጉ እና ይህን እሴት በእንደገናው ላይ ያክሉ።
4. አሁን የ [i] ን ቁጥር እንደ ቆጠራ ያዘምኑ (a [i]) = ቆጠራ (a [i]) + 1።
5. የሬስ ዋጋን ይመልሱ ፡፡

ለጥሩ ጥንዶች ቁጥር Leetcode መፍትሄ አተገባበር

C ++ ፕሮግራም

#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

ለጥሩ ጥንዶች Leetcode መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ሃሽ ካርታን በመጠቀም የእያንዳንዱን ንጥረ ነገር ብዛት ለማዘመን የማያቋርጥ ሥራ ስለምናከናውን ፣ ስለዚህ የጊዜ ውስብስብነት O (N) ይሆናል ፡፡

የቦታ ውስብስብነት 

ኦ (ኤን) የእያንዳንዱን ልዩ ንጥረ ነገሮች ብዛት ለማስቀመጥ ሃሽ ካርታ እየተጠቀምን ነው ፡፡ በጣም በከፋ ሁኔታ ውስጥ N የተለያዩ አካላት ሊኖሩ ይችላሉ።