ស្វែងរកស្ទួននៅក្នុងអារេដែលបានផ្តល់ឱ្យនៅពេលធាតុមិនត្រូវបានកំណត់ចំពោះជួរ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e ក្រុមហ៊ុន Amazon រោងចក្រ MAQ យូអេសជីអុបទិក
អារេ ហាសហាស។

បញ្ហា“ រកស្ទួននៅក្នុងអារេដែលបានផ្តល់នៅពេលដែលធាតុមិនត្រូវបានកំណត់ចំពោះជួរ” ចែងថាអ្នកមាន អារេ មាន n ចំនួនគត់។ សេចក្តីថ្លែងការណ៍បញ្ហាវាដើម្បីរកឱ្យឃើញធាតុស្ទួនប្រសិនបើមានវត្តមាននៅក្នុងអារេ។ ប្រសិនបើមិនមានធាតុបែបនេះត្រឡប់មកវិញទេ -1 ។

ឧទាហរណ៍

ស្វែងរកស្ទួននៅក្នុងអារេដែលបានផ្តល់ឱ្យនៅពេលធាតុមិនត្រូវបានកំណត់ចំពោះជួរ

[ 2, 4, 6, 2, 7, 8, 9, 7]
2, 7

ការពន្យល់

នៅក្នុងអារេទី ២ និងទី ៧ គឺជាធាតុស្ទួនតែមួយគត់។

[134, 567, 134, 456, 1000, 567, 7]
134, 567

ការពន្យល់

នៅក្នុងអារេទី ២ និងទី ៧ គឺជាធាតុស្ទួនតែមួយគត់។

ក្បួនដោះស្រាយដើម្បីរកធាតុស្ទួននៅក្នុងអារេមួយ

  1. ប្រកាស ផែនទី.
  2. រក្សាទុកធាតុរបស់អារេនិងប្រេកង់របស់វានៅក្នុងផែនទី។
  3. ប្រកាស ប៊ូលីន អថេរ ស្ទួន ដើម្បីពិនិត្យមើលថាតើធាតុស្ទួនមានឬអត់។
  4. បញ្ចូលលើផែនទីនិងពិនិត្យមើលថាតើធាតុណាដែលមានប្រេកង់ធំជាង ១ ។
  5. ប្រសិនបើប្រេកង់ធំជាង 1 បោះពុម្ពធាតុហើយចាប់ផ្តើមស្ទួនទៅជាការពិត។
  6. ពិនិត្យមើលថាតើលេខមួយស្ទួនមិនពិតប្រសិនបើលក្ខខណ្ឌពេញចិត្តបន្ទាប់មកបោះពុម្ព -1 ។

ការពន្យល់

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

យើងបានឆ្លងកាត់អំណះអំណាងពីរជាអារេនិងប្រវែងរបស់វា។ ឥឡូវប្រកាសអថេរមួយបន្ថែមទៀតដែលនឹងត្រូវបានប្តូរអថេរប៊ូលីន។ បន្ទាប់មកពិនិត្យវានៅពេលក្រោយប្រសិនបើយើងរកមិនឃើញធាតុស្ទួនណាមួយទេ ស្ទួន នៅតែមិនពិតវានឹងក្លាយជាការពិត។ បន្ទាប់មកប្រើផែនទីនេះរកឃើញធាតុដែលមានប្រេកង់ធំជាង ១ យើងនឹងបោះពុម្ពធាតុទាំងនោះ។ នោះហើយជារបៀបដែលយើងរកឃើញធាតុស្ទួននៅក្នុងជួរមួយ។

ចូរយើងពិចារណាឧទាហរណ៍មួយ៖

មកដល់ [] = {២,៤,៦,៣,១,២,៤,៧};

i = 0, មកដល់ [ខ្ញុំ] = ២; freq = {2: 2}

i=1, arr[i]=4; freq={2:1,4:1}

i=2, arr[i]=6; freq={2:1,4:1,6:1}

i=3, arr[i]=3; freq={2:1,4:1,6:1,3:1}

i=4, arr[i]=1; freq={2:1,4:1,6:1,3:1,1:1}

i = 5, មកដល់ [ខ្ញុំ] = 2; freq = {2: 2,4: 1,6: 1,3: 1,1: 1} // បង្កើនភាពញឹកញាប់នៃ '2' ពី 1 ដល់ 2,

i = 6, មកដល់ [ខ្ញុំ] = 4; freq = {2: 2,4: 2,6: 1,3: 1,1: 1} // បង្កើនភាពញឹកញាប់នៃ '4' ពី 1 ដល់ 2,

i=7, arr[i]=7; freq={2:2,4:2,6:1,3:1,1:1,7:1}

យើងមានផែនទីស្កេតនៅលើផែនទី៖ {២: ២,៤: ២,៦: ១.៣: ១,១: ១: ១}

ឥលូវនេះវាមាននៅលើផែនទីហើយឃើញថាតម្លៃណាដែលមានប្រេកង់ធំជាង ១ ។ យើងបានចាប់ផ្តើមអថេរប៊ូលីនដែលស្ទួនរួចហើយមិនពិតដូច្នេះពេលយើងពិនិត្យមើលប្រេកង់ធំជាង ១ យើងនឹងធ្វើបច្ចុប្បន្នភាពស្ទួនជាការពិត។ ហើយប្រសិនបើយើងចេញពីរង្វិលជុំដែលស្ទួនមិនពិតវាមានន័យថាធាតុស្ទួនមិនមាននៅក្នុងអារេទេ។

ច្បាស់ណាស់ថាទី ២ និងទី ៤ មានប្រេកង់ធំជាងន័យថាវាជាធាតុស្ទួន។

ហើយលទ្ធផលរបស់យើងក្លាយជា [២ ៤] ។ ដូច្នេះនេះគឺជាឧទាហរណ៍មួយពីរបៀបដែលយើងរកឃើញធាតុស្ទួននៅក្នុងអារេមួយ។

លេខកូដ

កូដ C ++ ដើម្បីរកធាតុស្ទួនគ្នាក្នុងអារេមួយ

#include <iostream>
#include <unordered_map>

using namespace std;

void getDuplicate(int arr[], int n)
{
    unordered_map<int,int> freq;

    for(int index=0;index<n;index++)
        freq[arr[index]]++;

    bool duplicate=false;
    unordered_map<int,int> :: iterator itr;
    for(itr=freq.begin();itr!=freq.end();itr++)
    {
        if(itr->second > 1)
        {
            cout<<itr->first<<" ";
            duplicate=true;
        }
    }
    if(!duplicate)
        cout<<"-1"<<endl;
}
int main()
{
    int arr[]={2,4,6,3,1,2,4,7};
    int n=sizeof(arr)/sizeof(arr[0]);
    getDuplicate(arr,n);
    return 0;
}
4 2

កូដចាវ៉ាដើម្បីរកធាតុស្ទួនគ្នាក្នុងអារេមួយ

import java.util.HashMap;
class findDuplicateNumber
{
    public static void getDuplicate(int arr[], int n)
    {
        HashMap<Integer, Integer> freq=new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i],freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i],1);
            }
        }
        boolean duplicate=false;
        for(int i:freq.keySet())
        {
            if(freq.get(i)> 1)
            {
                System.out.print(i+" ");
                duplicate=true;
            }
        }
        if(!duplicate)
            System.out.println("-1");
    }
    public static void main(String [] args)
    {
        int arr[]= {2,4,6,3,1,2,4,7};
        int len=arr.length;
        getDuplicate(arr,len);
    }
}
2 4

ការវិភាគស្មុគស្មាញ

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ដូច្នេះ“ រកស្ទួននៅក្នុងអារេដែលបានផ្តល់ឱ្យនៅពេលដែលធាតុមិនត្រូវបានកំណត់ចំពោះជួរ” បញ្ហាមានពេលវេលាស្មុគស្មាញ។

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ភាពស្មុគស្មាញនៃអវកាសក៏ជាលីនេអ៊ែរដែរព្រោះក្នុងករណីដ៏អាក្រក់បំផុតយើងអាចមានធាតុខុសគ្នាទាំងអស់។