ចំនួនដំណោះស្រាយល្អឡៃកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ក្រុមហ៊ុន Microsoft
អារេ ហាសហាស។ គណិតវិទ្យា

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះចំនួននៃចំនួនគត់ត្រូវបានផ្តល់ហើយយើងត្រូវរកចំនួនសរុបនៃគូល្អ (a [i], a [j]) ដែល a [i] = a [j] ។

ឧទាហរណ៍

nums = [1,2,3,1,1,3]
4

ការពន្យល់៖ មាន ៤ គូល្អនៅសន្ទស្សន៍ (០,៣), (០,៤), (៣,៤), (២,៥) ។

[1,1,1,1]
6

ការពន្យល់៖ គូនីមួយៗនៅក្នុងជួរគឺល្អ។

វិធីសាស្រ្ត (កម្លាំងដុសខាត់)

នៅក្នុងបញ្ហាដែលបានផ្តល់ឱ្យយើងអាចប្រើរង្វិលជុំពីរមួយសម្រាប់មួយ [i] និងទីពីរសម្រាប់ [ជ] នៃគូ។ ក្នុង​នេះ រង្វិលជុំនៅខាងក្នុង យើងនឹងនិយាយអំពីការរួមបញ្ចូលគ្នាដែលអាចធ្វើបានសម្រាប់គូ (a [i], a [j]) និងពិនិត្យមើលថាតើ [i] ស្មើនឹង [j] រឺអត់។

ក្បួនដោះស្រាយ៖

បង្កើតអថេររាប់និងចាប់ផ្តើមជាមួយសូន្យ។
2. ដំណើរការរង្វិលជុំដែលដាក់ក្នុងចន្លោះ, រង្វិលជុំខាងក្រៅសម្រាប់ [i] ពី i = 0 ដល់ i = n-1 និងរង្វិលជុំខាងក្នុងសម្រាប់ [j] ពី j = i + 1 ដល់ j = n-1 ។
3. ប្រសិនបើ a [i] = a [j] បន្ថែមគូបច្ចុប្បន្នដើម្បីរាប់ដោយបង្កើនគុណតម្លៃរបស់វាដោយ ១ ។
ត្រឡប់តម្លៃនៃអថេររាប់។

ការអនុវត្តសម្រាប់ចំនួននៃគូឡៃឡាក់កូដដំណោះស្រាយ

កម្មវិធី 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

ការវិភាគភាពស្មុគស្មាញសម្រាប់ចំនួននៃគូឡៃដិចសូលូសិន

ស្មុគស្មាញពេលវេលា

O (N ^ ២)៖ ដែល N ជាទំហំនៃអារេដែលបានផ្តល់។ នៅពេលដែលយើងកំពុងប្រើរង្វិលជុំចំនួនពីរនិងពិនិត្យមើលការបញ្ចូលគ្នានៃធាតុទាំងអស់នៅសន្ទស្សន៍ i និង j ភាពស្មុគស្មាញនៃពេលវេលានឹងមានអូ (N ^ 2)

ភាពស្មុគស្មាញនៃលំហ 

O (១)៖ យើងមិនប្រើការចងចាំបន្ថែមទេ។

 

វិធីសាស្រ្ត (ប្រសើរបំផុត)

យើងអាចបង្កើនប្រសិទ្ធភាពដំណោះស្រាយដោយប្រើ ផែនទីហាស។ មិនមានការប្រើវាលើគូនៃគូ i * j រាល់ដងទេ។ យើងត្រូវរាប់តែធាតុស្មើគ្នា។
ឧទាហរណ៍ប្រសិនបើយើងមានចំនួនធាតុជាក់លាក់មួយនៅក្នុងអារេយើងអាចគណនាចំនួនមធ្យោបាយសរុបក្នុងការជ្រើសរើសយកធាតុពីរនៅក្នុងសំណុំនៃធាតុស្រដៀងគ្នានេះ។
សម្រាប់អ្វីដែលយើងអាចធ្វើបានគឺយើងអាចធ្វើវាបានពីធាតុទី ១ និងធ្វើបច្ចុប្បន្នភាពចំនួនធាតុនីមួយៗនៅគ្រប់ជំហាន។
នៅពេលណាដែលយើងរកឃើញធាតុយើងនឹងពិនិត្យមើលថាតើមានធាតុស្រដៀងគ្នាជាច្រើនដែលមានរួចហើយមុនពេលធាតុនេះប្រើអថេររាប់ផែនទី។ ដូច្នេះវាអាចបង្កើតជាគូជាមួយធាតុដែលបានកើតឡើងពីមុនទាំងអស់។
យើងនឹងបន្ថែមការរាប់នោះទៅនឹងលទ្ធផលរបស់យើងនិងធ្វើបច្ចុប្បន្នភាព (បង្កើន) ចំនួនធាតុបច្ចុប្បន្នដោយ +1 ។

ចំនួនដំណោះស្រាយល្អឡៃកូដ

ក្បួនដោះស្រាយ៖
បង្កើតផែនទីមានចំនួនគត់និងចំនួនគត់ដែលគ្រាប់ចុចគឺធាតុនិងតម្លៃគឺជាចំនួនបច្ចុប្បន្ននៃធាតុនោះ។
2. ដំណើរការរង្វិលជុំសម្រាប់ធាតុនីមួយៗនៃទម្រង់ i = 0 ដល់ n-1 ។
3. រកចំនួន (a [i]) មុនពេលដាក់វាចូលទៅក្នុងផែនទីហើយបន្ថែមតម្លៃនេះទៅតម្លៃលក់បន្ត
4. ឥឡូវធ្វើបច្ចុប្បន្នភាពចំនួន a [i] ជាការរាប់ (a [i]) = រាប់ (a [i]) + 1 ។
5. ត្រឡប់តម្លៃនៃ res ។

ការអនុវត្តសម្រាប់ចំនួននៃគូឡៃឡាក់កូដដំណោះស្រាយ

កម្មវិធី 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

ការវិភាគភាពស្មុគស្មាញសម្រាប់ចំនួននៃគូឡៃដិចសូលូសិន

ស្មុគស្មាញពេលវេលា

O (N)៖ នៅពេលដែលយើងកំពុងធ្វើការងារថេរក្នុងការធ្វើបច្ចុប្បន្នភាពចំនួនធាតុនីមួយៗដោយប្រើហាស់ផែនទីដូច្នេះភាពស្មុគស្មាញនៃពេលវេលានឹងជា O (N) ។

ភាពស្មុគស្មាញនៃលំហ 

O (N) ៖ យើងកំពុងប្រើផែនទីហាស់ដើម្បីរក្សាទុកចំនួនធាតុដែលមានតែមួយគត់។ វាអាចមានធាតុផ្សេងគ្នា N ក្នុងករណីអាក្រក់បំផុត។