អារេអតិបរមាពីអារេពីរដែលបានផ្តល់ឱ្យរក្សាលំដាប់ដូចគ្នា  


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ Accenture ក្រុមហ៊ុន Amazon ដេលីវ៉ាយ រោងចក្រ Fourkites បន្ទប់អូយ ការផ្សព្វផ្សាយជាសាធារណៈ Zoho
អារេ ហាស់

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

ឧទាហរណ៍  

បញ្ចូល:

int arr1 [] = {៣.៧,៩,១,៤}

int arr2 [] = {៣.៧,៩,១,៤}

លទ្ធផល:

{៥០, ៥០, ៥០, ០, ០}

ការពន្យល់:

ក្នុងនាមជា ៧, ៩ គឺជាធាតុនៅក្នុងអារេដំបូងដូច្នេះវាចេញមកដំបូងក្នុងលទ្ធផល។

បញ្ចូល:

int arr1 [] = {៣.៧,៩,១,៤}

int arr2 [] = {៣.៧,៩,១,៤}

លទ្ធផល:

{៧, ៨, ៩}

ក្បួនដោះស្រាយសម្រាប់អារេអតិបរមាពីអារេពីរដែលបានផ្តល់ឱ្យរក្សាលំដាប់ដូចគ្នា  

  1. បំលែងអារេទាំងពីរទៅក្នុងបញ្ជីឈ្មោះ វ៉ិចទ័រ.
  2. តម្រៀបវ៉ិចទ័រទាំងពីរក្នុងលំដាប់មិនឡើង។
  3. ឆ្លងកាត់វ៉ិចទ័រទាំងពីរក្នុងពេលដំណាលគ្នានិងរុញតម្លៃវ៉ិចទ័រធំជាងទៅក្នុងផែនទីរួមជាមួយប្រេកង់របស់ធាតុ។
  4. បង្កើតវ៉ិចទ័រថ្មីមួយ "លទ្ធផល" ។
  5. ពិនិត្យមើលថាតើមានធាតុទូទៅមួយនៅក្នុងឯកសារ a ផែនទី ហើយនៅក្នុងអារេដំបូងបន្ទាប់មកបន្ថែមធាតុនោះទៅក្នុងវ៉ិចទ័រលទ្ធផល។
  6. ពិនិត្យមើលប្រសិនបើមានធាតុទូទៅមួយនៅក្នុងផែនទីហើយក៏នៅក្នុងអារេទីពីរបន្ទាប់មកជ្រើសរើសធាតុដែលមានប្រេកង់គឺ 1 ហើយបន្ថែមវាទៅវ៉ិចទ័រលទ្ធផល។
  7. ព្រីនវ៉ិចទ័រលទ្ធផល "លទ្ធផល" ។
សូម​មើល​ផង​ដែរ
បញ្ច្រាសដង្កៀបអប្បបរមា

ការពន្យល់  

បំលែងអារេទាំងពីរទៅជាវ៉ិចទ័រហើយតម្រៀបវាតាមលំដាប់ថយចុះ។ ជាមួយនេះយើងអាចទទួលបានតម្លៃនៃអារេទាំងពីរទៅជាវ៉ិចទ័រហើយយើងមានលេខធំជាងមុនតាមលំដាប់រៀងនៃវ៉ិចទ័រទាំងពីរ។ ដូច្នេះយើងអាចជ្រើសរើស 'n' ចំនួនអតិបរមា ពីអារេទាំងពីរ។

ដើម្បីដោះស្រាយករណីនៃធាតុធម្មតាអ្វីដែលយើងនឹងធ្វើគឺប្រៀបធៀបវ៉ិចទ័រនិងជ្រើសរើសអតិបរមាពីអារេទាំងពីរហើយដាក់វាទៅក្នុងផែនទីជាមួយនឹងប្រេកង់របស់ពួកគេដោយនេះយើងអាចរក្សាភ្នែកបានប្រសិនបើអាច ជាធាតុធម្មតាយើងនឹងជំរុញធាតុអតិបរិមាចូលទៅក្នុងផែនទីប្រសិនបើយើងរកឃើញធាតុមួយច្រើនជាងនេះយើងនឹងបង្កើនប្រេកង់របស់ពួកគេហើយពួកគេនឹងមិនត្រូវបានរាប់ជាធាតុបន្ថែមនៅក្នុងផែនទីទេពួកគេនឹង សម្គាល់ថាប្រេកង់ទី ២, ៣ រឺច្រើនជាងនេះ .. ដូច្នេះនៅក្នុងដំណើរឆ្លងកាត់ពេលក្រោយយើងអាចមិនអើពើនឹងវាហើយអាចផ្តល់អាទិភាពដល់អារេដំបូង។

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

សូម​មើល​ផង​ដែរ
លេខជាប់គ្នាអតិបរមាបង្ហាញជាអារេ

ការអនុវត្តន៍  

កម្មវិធី C ++ សំរាប់អារេអតិបរិមាពីអារេរក្សាលំដាប់លំដោយដូចគ្នា

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

void makeGreaterFirstArray(int A[], int B[], int n)
{
    vector<int> V1(A, A+n);
    vector<int> V2(B, B+n);
    sort(V1.begin(), V1.end(), greater<int>());
    sort(V2.begin(), V2.end(), greater<int>());

    unordered_map<int, int> MAP;
    int i = 0, j = 0;
    while (MAP.size() < n)
    {
        if (V1[i] >= V2[j])
        {
            MAP[V1[i]]++;
            i++;
        }
        else
        {
            MAP[V2[j]]++;
            j++;
        }
    }
    vector<int> output;
    for (int i = 0; i < n; i++)
        if (MAP.find(A[i]) != MAP.end())
            output.push_back(A[i]);

    for (int i = 0; i < n; i++)
        if (MAP.find(B[i]) != MAP.end() && MAP[B[i]] == 1)
            output.push_back(B[i]);

    for (int i = 0; i < n; i++)
        cout << output[i] << " ";
}
int main()
{
    int arr1[] = {3,7,9,1,4};
    int arr2[] = {2,8,6,5,3};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    makeGreaterFirstArray(arr1, arr2, n);
    return 0;
}
7 9 8 6 5

កម្មវិធីចាវ៉ាសម្រាប់អារេអតិបរមាពីអារេរក្សាលំដាប់លំដោយដូចគ្នា

import java.util.Collections;
import java.util.Vector;
import java.util.HashMap;
import java.util.Arrays;
import java.util.stream.Collectors;

class findsubarray
{
    public static void makeGreaterFirstArray(int []A, int []B, int n)
    {
        Vector<Integer> V1 = new Vector<>();
        Vector<Integer> V2 = new Vector<>();

        Integer[] I1 = Arrays.stream( A ).boxed().toArray( Integer[]::new );
        Integer[] I2 = Arrays.stream( B ).boxed().toArray( Integer[]::new );


        Collections.addAll(V1, I1);
        Collections.addAll(V2, I2);

        Collections.sort(V1, Collections.reverseOrder());
        Collections.sort(V2, Collections.reverseOrder());


        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int i = 0, j = 0;
        while (MAP.size() < n)
        {
            if (V1.get(i) >= V2.get(j))
            {
                if(MAP.containsKey(V1.get(i)))
                {
                    MAP.put(V1.get(i), MAP.get(V1.get(i))+1);
                    i++;
                }
                else
                {
                    MAP.put(V1.get(i),1);
                    i++;
                }
            }
            else
            {
                if(MAP.containsKey(V2.get(j)))
                {
                    MAP.put(V2.get(j), MAP.get(V2.get(j))+1);
                    j++;
                }
                else
                {
                    MAP.put(V2.get(j),1);
                    j++;
                }
            }
        }
        Vector<Integer> output = new Vector<Integer>();

        for (int a = 0; a < n; a++)
            if (MAP.containsKey(A[a]))
                output.add(A[a]);

        for (int b = 0; b < n; b++)
            if (MAP.containsKey(B[b]) && MAP.get(B[b])==1)
                output.add(B[b]);


        System.out.println(output);
    }
    public static void main(String [] args)
    {
        int arr1[] = {3,7,9,1,4};
        int arr2[] = {2,8,6,5,3};
        int n = arr1.length;
        makeGreaterFirstArray(arr1, arr2, n);
    }
}
[7, 9, 8, 6, 5]

ការវិភាគស្មុគស្មាញសម្រាប់អារេអតិបរមាពីអារេពីរដែលបានផ្តល់ឱ្យរក្សាលំដាប់ដូចគ្នា  

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

O (n log n) ដែលជាកន្លែងដែល “ n” គឺជាប្រវែងនៃអារេ។

សូម​មើល​ផង​ដែរ
ចម្ងាយអតិបរមានៅអារេ

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

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាប្រវែងនៃអារេ។