មានផ្ទុកដំណោះស្រាយឌុយលេខកូដឌែរទី ២


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon Facebook ក្រុមហ៊ុន google
អារេ ហាសហាស។ រអិលបង្អួច

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

នៅក្នុងបញ្ហានេះយើងត្រូវបានផ្តល់ឱ្យ អារេ នៃចំនួនគត់ហើយយើងត្រូវពិនិត្យមើលថាតើមានធាតុស្ទួនណាមួយដែលមានចម្ងាយយ៉ាងតិចដែរឬទេ k រវាងគ្នានឹងគ្នា។
ឧទាហរណ៍ភាពខុសគ្នារវាងសូចនាករនៃធាតុដូចគ្នាទាំងពីរគួរតែតិចជាង k ។
ឬ,  nums [ខ្ញុំ] == លេខ [j] និង abs (ij) <= k

ឧទាហរណ៍

nums = [1,2,3,1], k = 3
true

ការពន្យល់:

ធាតុនៅលិបិក្រម ០ និង ៣ គឺដូចគ្នាហើយ ៣ - ០ <= k ។

nums = [1,2,3,1,2,3], k = 2
false

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

ប្រសិនបើយើងនិយាយអំពីវិធីសាស្រ្តប្រើកម្លាំងដាប់ប៊ែលយើងអាចអនុវត្តកម្មវិធីដោយប្រើរង្វិលជុំចំនួនពីរហើយពិនិត្យមើលធាតុនីមួយៗនៃអារេទៅចំងាយ k ពីចម្ងាយពីវាថាតើមានធាតុណាមួយមានរឺអត់។
ប្រសិនបើធាតុណាមួយត្រូវបានរកឃើញដូចគ្នាទៅនឹងធាតុបច្ចុប្បន្ននោះយើងនឹងត្រឡប់ជាការពិតបើមិនដូច្នេះទេយើងត្រឡប់មិនពិត។

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

  1. ដំណើរការរង្វិលជុំសម្រាប់គ្រប់ធាតុទាំងអស់ ចំនួន [ខ្ញុំ] នៃអារេដែលបានផ្តល់ឱ្យ។
  2. នៅខាងក្នុងរង្វិលជុំនេះរត់ម្តងទៀតសម្រាប់រង្វិលជុំនិងឆ្លងកាត់ធាតុទាំងអស់ពី j = ខ្ញុំ + ១ ទៅ j = i + k ហើយប្រៀបធៀបតម្លៃរបស់វាទៅនឹងឯកសារ nums [ខ្ញុំ] ។
    • If nums [ច] == ចំនួន [ខ្ញុំ] បន្ទាប់មកត្រឡប់ជាការពិត។ ដូចដែលយើងបានរកឃើញធាតុមួយ។
  3. ទីបំផុតនៅពេលរកមិនឃើញធាតុស្ទួនណាមួយបន្ទាប់មកត្រឡប់មិនពិតមុនពេលចាកចេញពីមុខងារ។

ការអនុវត្តសម្រាប់ផ្ទុកនូវដំណោះស្រាយលេខពីរស្ទួនលេខឌែរកូដ

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    for(int i=0;i<nums.size();i++)
        for(int j=i+1;j<nums.size() && j<=i+k;j++)
        {
            if(nums[j]==nums[i])
                return true;
        }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

កម្មវិធីចាវ៉ា

class Rextester{
    
    public static boolean containsNearbyDuplicate(int[] nums, int k) 
    {
        for(int i=0;i<nums.length;i++)
            for(int j=i+1;j<nums.length && j<=i+k;j++)
            {
                if(nums[j]==nums[i])
                    return true;
            }

        return false;

    }
    
    public static void main(String args[])
    {
       	int[] nums={1,2,3,1};
        int k=3;
        System.out.println(containsNearbyDuplicate(nums,k) );
    }
}
true

ការវិភាគស្មុគស្មាញសម្រាប់ផ្ទុកនូវដំណោះស្រាយឌុយហ្សែនទី ២

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

O (n * នាទី (k, n))៖ យើងកំពុងឆ្លងកាត់ធាតុអប្បបរមា (k, n) សម្រាប់ធាតុទាំងអស់នៃអារេ។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលានឹងមានអូ (n * នាទី (k, n)) ។

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

O (១)៖ ទំហំថេរ។

វិធីសាស្រ្តទី ២ (ផ្ទាំងរអិល)

ដូចដែលយើងអាចឃើញថាយើងនឹងចំណាយពេលច្រើនជាងមួយដងទៅនឹងធាតុនៃអារេដែលបង្កើនភាពស្មុគស្មាញនៃពេលវេលារបស់វា។ យើងគួរទៅលេងតែម្ដងទៅធាតុនីមួយៗសម្រាប់កាត់បន្ថយពេលវេលាដល់អូ (n) ។

សម្រាប់អ្វីដែលយើងអាចធ្វើបានគឺយើងអាចរក្សាបង្អួចរអិលមុន ៗ k ធាតុដោយប្រើហាសកំណត់រាល់ពេលដែលយើងកំពុងទស្សនាធាតុណាមួយនៃអារេ។ ដោយធ្វើដូចនេះយើងអាចពិនិត្យមើលយ៉ាងងាយស្រួលពីសំណុំនៃធាតុ k មុនប្រសិនបើមានធាតុមួយនៅក្នុងសំណុំដែលដូចគ្នានឹងធាតុបច្ចុប្បន្នដែលយើងកំពុងទស្សនា។ ប្រសិនបើយើងបានរកឃើញមួយនៅក្នុងសំណុំ, បន្ទាប់មកនៅពេលនោះយើងត្រឡប់មកវិញពិត។ ផ្សេងទៀតយើងនឹងបញ្ចូលធាតុបច្ចុប្បន្ននៅក្នុងសំណុំហើយក៏យកធាតុដែលបានចូលមើលចុងក្រោយចេញពីសំណុំដូច្នេះយើងតែងតែមាន k ធាតុមុននៅក្នុងសំណុំរបស់យើង។

អនុញ្ញាតឱ្យមើលឃើញឧទាហរណ៍នៅក្នុងតួលេខខាងក្រោម:

មានផ្ទុកដំណោះស្រាយឌុយលេខកូដឌែរទី ២

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

  1. បង្កើត ហាស់សិត សម្រាប់ទុក k ធាតុមុន។
  2. ឆ្លងកាត់រាល់ធាតុលេខ [i] នៃអារេដែលបានផ្តល់នៅក្នុងរង្វិលជុំ។
    • ពិនិត្យមើលថាតើឈុតបានមានលេខ [i] រួចហើយឬអត់។ ប្រសិនបើលេខ [i] មានវត្តមាននៅក្នុងសំណុំ (មានន័យថាធាតុស្ទួនមានវត្តមាននៅចម្ងាយតិចជាងស្មើ k ) បន្ទាប់មកត្រលប់មកវិញជាការពិត។ អ្នកផ្សេងបន្ថែមលេខ [i] ទៅសំណុំ។
    • ប្រសិនបើទំហំនៃឈុតធំជាង k បន្ទាប់មកយកធាតុដែលបានចូលទៅចុងក្រោយ (លេខ [ik]) ចេញពីសំណុំ។
  3. ទីបំផុតនៅពេលរកមិនឃើញធាតុស្ទួនណាមួយបន្ទាប់មកត្រឡប់មិនពិតមុនពេលចាកចេញពីមុខងារ។

ការអនុវត្តសម្រាប់ផ្ទុកនូវដំណោះស្រាយលេខពីរស្ទួនលេខឌែរកូដ

កម្មវិធី C ++

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

កម្មវិធីចាវ៉ា

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

ការវិភាគស្មុគស្មាញសម្រាប់ផ្ទុកនូវដំណោះស្រាយឌុយហ្សែនទី ២

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

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

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

អូ (នាទី (k, n))៖ យើងកំពុងរក្សាទុកធាតុ k នៅអតិបរិមានៅក្នុងសំណុំហាស។ ប្រសិនបើ k> n ពេលនោះមានតែធាតុ n ប៉ុណ្ណោះដែលនឹងត្រូវបានរក្សាទុកក្នុងសំណុំអតិបរិមា។