ធាតុទីមួយកើតឡើង k ដងក្នុងអារេមួយ  


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ការដំឡើង PayU មន្ទីរពិសោធន៍អេសអេស តេរ៉ាតាតា Wipro Yatra Zoho
អារេ ហាស់

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

ឧទាហរណ៍  

រកឃើញធាតុដែលបាត់នៃជួរមួយពិន

Arr[]={1,4,5,2,4,2,7},  k=2
4

ការពន្យល់

ក្នុងឧទាហរណ៍នេះមានធាតុពីរដែលកើតឡើងដង k ។ ៤ និង ២ មានចំនួន k ដងប៉ុន្តែ ៤ ជាដំបូងដែលកើតឡើង k ដង។ ដូច្នេះយើងត្រឡប់ ៤ ។

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

  1. ប្រកាសក ហាស់ម៉ាប់.
  2. ឆ្លងកាត់អារេ។
    • រាប់និងទុកប្រេកង់នៃធាតុនីមួយៗនៃអារេទៅក្នុងផែនទី។
  3. ឆ្លងកាត់អារេម្តងទៀតហើយពិនិត្យមើលថាតើប្រេកង់របស់ធាតុអារេនីមួយៗស្មើនឹង k ។
    • ប្រសិនបើលក្ខខណ្ឌពេញចិត្តបន្ទាប់មកត្រឡប់ធាតុ។

ការពន្យល់

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

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

សូម​មើល​ផង​ដែរ
រកដំណោះស្រាយ Leetcode ខុសគ្នា

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

មកដល់ [] = {2,4,6,4,2,1,}, k = 2

យើងនឹងរក្សាទុកធាតុនានាជាកូនសោរនិងប្រេកង់របស់វាជាតម្លៃទៅក្នុងផែនទីបន្ទាប់ពីរក្សាទុកផែនទីរបស់យើងនឹងមានតម្លៃដូចខាងក្រោម៖

myMap={1:1, 2:2, 4:2, 6:1};

យើងនឹងពិនិត្យមើលធាតុអារេនីមួយៗចាប់ផ្តើមពីសន្ទស្សន៍លេខ ០ យើងនឹងចាប់ផ្តើមឆ្លងកាត់អារេ

ខ្ញុំ = ០,

ប្រសិនបើប្រេកង់នៃអារេនីមួយៗ [i] == គ៖

ប្រេកង់នៃលេខ ២ គឺ ២ ដែលស្មើនឹង k វាក៏ជាធាតុដែលមានមុនដែរដោយមិនមានអ្វីកើតឡើងដូច្នេះយើងត្រឡប់ការមកដល់ហើយខ្ញុំនឹងចេញលទ្ធផល ២ ។

ក្នុងករណីប្រសិនបើប្រេកង់ណាមួយនៃធាតុមិនត្រូវគ្នានឹង 'k' នោះយើងនឹងត្រឡប់ -1 ។

លេខកូដ  

កូដ C ++ ដើម្បីរកធាតុដំបូងដែលកើតឡើង k ដងក្នុងអារេមួយ

#include<iostream>
#include <unordered_map>

using namespace std;

int firstElement(int arr[], int n, int k)
{
    unordered_map<int, int> freqMap;

    for (int i=0; i<n; i++)
        freqMap[arr[i]]++;

    for (int i=0; i<n; i++)
        if (freqMap[arr[i]] == k)
            return arr[i];

    return -1;
}
int main()
{
    int arr[] = {2,4,6,4,2,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}
2

កូដចាវ៉ាដើម្បីរកធាតុដំបូងដែលកើតឡើង k ដងក្នុងអារេមួយ

import java.util.HashMap;

class firstKOccuringElement
{
    public static int getFirstElement(int arr[], int n, int k)
    {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(freqMap.containsKey(arr[i]))
            {
                freqMap.put(arr[i], freqMap.get(arr[i])+1);
            }
            else
            {
                freqMap.put(arr[i], 1);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (freqMap.get(arr[i]) == k)
            {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,6,4,2,1,6};
        int n = arr.length;
        int k = 2;
        System.out.println(getFirstElement(arr, n, k));
    }
}
2

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

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ នៅទីនេះដោយសារយើងបានប្រើហាសយើងអាចអនុវត្តប្រតិបត្តិការបានក្នុងរយៈពេល O ។

សូម​មើល​ផង​ដែរ
បោះពុម្ពធាតុប្លែកៗទាំងអស់នៃអារេចំនួនគត់ដែលបានផ្តល់ឱ្យ

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

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