Leetcode шийдлийн сайн хосуудын тоо


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Microsoft-
Array Хаширч байна Математик

Асуудлын мэдэгдэл

Энэ бодлогод бүхэл тоон массив өгөгдсөн бөгөөд бид сайн хосуудын нийт тоог (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

Тайлбар: Массивын хос бүр сайн байна.

Хандлага (Brute Force)

Өгөгдсөн бодлогод бид хоёр давталтыг ашиглаж болно, нэг нь [i], хоёр дахь нь [j] хосын хувьд. Энэ нь үүрлэсэн гогцоо бид (a [i], a [j]) хосын бүх боломжит хослолыг давтаж, [i] нь [j] -тэй тэнцэх эсэхийг шалгана.

Алгоритм:

1. Тоолуурын хувьсагчийг үүсгээд тэгээр эхлүүлнэ.
2. Оруулсан гогцоо, i = 0-ээс i = n-1 хүртэлх [i] гадна гогцоог, j = i + 1-ээс j = n-1 хүртэл [j] -тэй дотоод гогцоог ажиллуулна.
3. Хэрэв a [i] = a [j] бол түүний утгыг 1-ээр нэмэгдүүлэн тоолохын тулд одоогийн хосыг нэмнэ.
4. count хувьсагчийн утгыг буцаана.

Олон тооны хос хослолын 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 шийдлийн тооны сайн хосуудын нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N ^ 2): N бол тухайн массивын хэмжээ юм. Бид хоёр гогцоог ашиглаж, i ба j индекс дээрх бүх элементийн хослолыг шалгаж байх үед хугацааны нарийн төвөгтэй байдал O (N ^ 2) болно.

Сансрын нарийн төвөгтэй байдал 

O (1): Бид нэмэлт санах ой ашиглахгүй байна.

 

Хандалт (оновчтой)

Бид ашиглан шийдлийг оновчтой болгох боломжтой Хэш газрын зураг. Бүх хос хослолууд дээр i * j удаа давтах шаардлагагүй. Бид зөвхөн тэнцүү элементүүдийг л тоолох ёстой.
Хэрэв бид массив доторх тодорхой элементийг тоолсон бол ижил төстэй элементүүдийн аль нэг хоёр элементийг сонгох олон тооны аргыг тооцоолж болно.
Үүний тулд бид 1-р элементээс давтаж, элемент бүрийн тооллогыг алхам тутамд шинэчилж болно.
Бид элемент олох бүрт тоолох газрын зургийн хувьсагчийг ашиглан энэ элементээс өмнө хичнээн ижил төстэй элементүүд байсан болохыг шалгах болно. Ингэснээр өмнөх бүх элементүүдтэй хослуулах боломжтой болно.
Бид энэ тооллыг үр дүн дээрээ нэмж, одоогийн элементийн тоог +1-ээр шинэчлэх (нэмэгдүүлэх).

Leetcode шийдлийн сайн хосуудын тоо

Алгоритм:
1. Түлхүүр нь элемент бөгөөд утга нь тухайн элементийн одоогийн тоо болох бүхэл тоо ба бүхэл тоо бүхий Has-ийн газрын зургийг үүсгээрэй.
2. i = 0-ээс n-1 хүртэлх элемент бүрийн хувьд for for давталтыг ажиллуулна.
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 шийдлийн тооны сайн хосуудын нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N): Хэш Map ашиглан элемент бүрийн тооллогыг шинэчлэх ажлыг тогтмол хийж байгаа тул цаг хугацааны нарийн төвөгтэй байдал O (N) байх болно.

Сансрын нарийн төвөгтэй байдал 

O (N) : Бид өвөрмөц элемент бүрийн тооллыг хадгалахын тулд Hash Map ашиглаж байна. Хамгийн муу тохиолдолд N өөр өөр элемент байж болно.