Լավ զույգերի Leetcode լուծման քանակը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Microsoft
Դասավորություն Հեշինգ Մաթեմատիկա

Խնդիրի հայտարարություն

Այս խնդրում տրված է ամբողջ թվերի զանգված, և մենք պետք է պարզենք լավ զույգերի ընդհանուր թվաքանակը (a [i], a [j]), որտեղ a [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

Բացատրություն. Rayանգվածի յուրաքանչյուր զույգ լավն է:

Մոտեցում (կոպիտ ուժ)

Տրված խնդրում կարող ենք օգտագործել երկու օղակ, մեկը զույգի [i] և երկրորդը զույգի [j]: Սրանում տեղադրված հանգույց մենք կկրկնվենք զույգի բոլոր հնարավոր համադրությունների համար (a [i], a [j]) և ստուգենք ՝ a [i] հավասար է [j], թե ոչ:

Ալգորիթմ

1. Ստեղծել հաշվարկի փոփոխական և նախաստորագրել զրոյով:
2. Գործարկել տեղադրված հանգույց, արտաքին օղակը a [i] - ի համար i = 0-ից i = n-1 և ներքին օղակ a [j] - ի համար j = i + 1- ից j = n-1:
3. Եթե a [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

Java ծրագիր

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 լուծման համար

Timeամանակի բարդություն

O (N ^ 2): Որտեղ N- ը տրված զանգվածի չափն է: Քանի որ մենք օգտագործում ենք երկու օղակ և ստուգում ենք i և j ինդեքսում տարրերի բոլոր համակցությունները, ժամանակի բարդությունը կլինի O (N ^ 2):

Տիեզերական բարդություն 

O (1): Մենք ոչ մի լրացուցիչ հիշողություն չենք օգտագործում:

 

Մոտեցում (օպտիմիզացված)

Մենք կարող ենք լուծումն օպտիմալացնել ՝ օգտագործելով Հաշ քարտեզ, I * j անգամների զույգերի բոլոր զուգորդումների վրա կրկնություն օգտագործելը չկա: Մենք պետք է հաշվենք միայն հավասար տարրերը:
այսինքն, եթե զանգվածում ունենք որոշակի տարրի հաշվարկ, մենք կարող ենք հաշվարկել նմանատիպ տարրերի այս հավաքածուի ցանկացած երկու տարր ընտրելու եղանակների ընդհանուր քանակը:
Դրա համար այն, ինչ մենք կարող ենք անել, այն է, որ մենք կարող ենք կրկնել 1-ին տարրից և յուրաքանչյուր քայլին թարմացնել յուրաքանչյուր տարրի հաշվարկը:
Երբ որևէ տարր ենք գտնում, մենք ստուգելու ենք, թե քանի նման տարրեր են արդեն առկա այս տարրից առաջ ՝ օգտագործելով հաշվարկի քարտեզի փոփոխական: Որպեսզի այն կարողանա զույգ կազմել նախորդ բոլոր պատահած տարրերի հետ:
Մենք այդ արդյունքը կավելացնենք մեր արդյունքին և թարմացնենք (ավելացնենք) ընթացիկ տարրի հաշվարկը +1-ով:

Լավ զույգերի Leetcode լուծման քանակը

Ալգորիթմ:
1. Ստեղծեք «Հասարակության» և «Ամբողջ թվերի» քարտեզ, որի բանալին տարրն է և արժեքը `տվյալ տարրի ընթացիկ հաշվարկը:
2. Յուրաքանչյուր տարրի ձևով գործարկեք for = i = 0-ից n-1 ձևի համար:
3. Գտեք հաշվիչը (a [i]) նախքան այն քարտեզի մեջ դնելը և այս արժեքը ավելացրեք res- ին:
4. Այժմ թարմացրեք a [i] -ի քանակը որպես count (a [i]) = count (a [i]) + 1:
5. Վերադարձրու res- ի արժեքը:

Իրականացում լավ զույգերի համար 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

Java ծրագիր

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 լուծման համար

Timeամանակի բարդություն

ՎՐԱ) : Քանի որ մենք անընդհատ աշխատանք ենք կատարում Hash Map- ի միջոցով յուրաքանչյուր տարրի հաշվարկի թարմացման ուղղությամբ, ուստի ժամանակի բարդությունը կլինի O (N):

Տիեզերական բարդություն 

ՎՐԱ) Մենք օգտագործում ենք Hash Map յուրաքանչյուր եզակի տարրերի հաշվարկը պահելու համար: Վատագույն դեպքում կարող են լինել N տարբեր տարրեր: