ប្រតិបត្ដិការលុបអប្បបរមាដើម្បីធ្វើឱ្យធាតុទាំងអស់នៃអារេដូចគ្នា  


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e រោងចក្រ
អារេ ហាស់

ឧបមាថាយើងមានធាតុចូល អារេ ជាមួយ "X" ចំនួននៃធាតុ។ យើងបានផ្តល់នូវបញ្ហាដែលយើងត្រូវរកឱ្យឃើញនូវប្រតិបត្ដិការលុបចោលដែលគួរតែជាអប្បបរមាដែលត្រូវការដើម្បីបង្កើតអារេស្មើពោលគឺអារេនឹងមានធាតុស្មើគ្នា។

ឧទាហរណ៍  

បញ្ចូល:

[១, ៤, ៦, ២, ១]

លទ្ធផល:

3

ការពន្យល់:

បន្ទាប់ពីដកចេញ (៤, ៦, ២) ៣ ធាតុអារេប្រែជាស្មើពោលគឺ [១, ១, ១]

បញ្ចូល:

[១, ៤, ៦, ២, ១]

លទ្ធផល:

5

ការពន្យល់:

យើងអាចដកធាតុណាមួយក្នុងចំណោមធាតុទាំង ៥ ចេញដើម្បីឱ្យវាក្លាយជាអារេស្មើគ្នា។

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

  1. ទុកប្រេកង់នៃធាតុទាំងអស់នៃអារេនៅក្នុងផែនទី។
  2. កំណត់ “ អតិបរមា_freq” ទៅ INT_MIN.
  3. បញ្ចូលលើផែនទីនិងពិនិត្យមើលថាតើធាតុណាដែលមានប្រេកង់អតិបរមា។
    • កំណត់ “ អតិបរមា_freq” ទៅ អតិបរមា (អតិបរិមា, តម្លៃ) ដើម្បីរកតម្លៃអតិបរិមាក្នុងចំណោមប្រេកង់ទាំងអស់។
  4. ត្រឡប់ភាពខុសគ្នារវាងទំហំអារេ “ n” និង max_freq (n - max_freq).

ការពន្យល់  

យើងបានផ្តល់បញ្ហាដែលយើងត្រូវរកចំនួនអប្បបរមា លុប ប្រតិបត្ដិការត្រូវបានទាមទារដើម្បីធ្វើឱ្យអារេស្មើ (នៃធាតុស្រដៀងគ្នា) ។ ចំពោះបញ្ហានេះយើងនឹងប្រើផែនទីដើម្បីរក្សាទុកឯកសារ ប្រេកង់។ នៃលេខនីមួយៗដែលមាននៅក្នុងជួរអារេ។

សូម​មើល​ផង​ដែរ
ពិនិត្យ Palindrome បន្ទាប់ពីរាល់សំណួរជំនួសតួអក្សរ

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

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

មកដល់: {១០, ៣, ៤, ៤, ២, ៤};

  • i = 0, វាត្រូវចំណាយពេល [i] ដូច ១០ ហើយផ្ទុក freq (១០, ១) ។
  • i = 1, វាត្រូវចំណាយពេល [i] ដូច ១០ ហើយផ្ទុក freq (១០, ១) ។
  • សម្រាប់ i = 2, វាត្រូវចំណាយពេល [i] ដែលជា 4 ហើយផ្ទុក freq (4, 1) ។
  • ខ្ញុំ = ៣, វាត្រូវការដល់ [ខ្ញុំ] ដូច ៤, ដោយសារ ៤ មានកន្លែងរួចហើយនៅក្នុងផែនទីវាគ្រាន់តែបន្ថែមការរាប់មួយបន្ថែមទៀតនៅកន្លែងសំខាន់ ៤ ហើយផ្ទុកឥវ៉ាន់ (៤, ២) ។
  • i = 4, វាយក arr [i] ជា 2 ហើយផ្ទុក freq (2, 1) ។
  • សម្រាប់ខ្ញុំ = ៥, វាត្រូវការដល់ [i] ដែលជា ៤, ចាប់តាំងពី ៤ មានកន្លែងរួចហើយនៅក្នុងផែនទីវាគ្រាន់តែបន្ថែមការរាប់មួយបន្ថែមទៀតនៅត្រង់ចំនុចសំខាន់ ៤ ហើយផ្ទុក freq (៤, ៣) ។

ក្នុងចំណោមលេខតែមួយគត់ '៤' នេះមានប្រេកង់អតិបរមាគឺ ៣ ហើយបន្ទាប់ពីឆ្លងកាត់និងស្វែងរកប្រេកង់អតិបរមា ៣ ពីផែនទីយើងនឹងត្រឡប់តម្លៃ (n - max_freq) នោះជាលទ្ធផលរបស់យើង។

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

កម្មវិធី C ++ សម្រាប់ប្រតិបត្តិការលុបអប្បបរមាដើម្បីបង្កើតធាតុទាំងអស់នៃអារេដូចគ្នា

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

int minDelete(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int max_freq = INT_MIN;

    for (auto itr = freq.begin(); itr != freq.end(); itr++)
        max_freq = max(max_freq, itr->second);

    return n - max_freq;
}
int main()
{
    int arr[] = { 10, 3, 4, 4, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minDelete(arr, n);
    return 0;
}
3

កម្មវិធីចាវ៉ាសម្រាប់ប្រតិបត្តិការលុបអប្បបរមាដើម្បីបង្កើតធាតុទាំងអស់នៃអារេដូចគ្នា

import java.util.HashMap;
class minimumDeletionOperation
{
    public static int noOfMinimumDeletions(int arr[], int n)
    {
        HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
        for(int i=0; i<arr.length; i++)
        {
            if(freq.containsKey(arr[i]))
                freq.put(arr[i], freq.get(arr[i]) + 1);
            else
                freq.put(arr[i], 1);
        }

        int max_freq=Integer.MIN_VALUE;

        for (int i:freq.keySet())
            max_freq = Math.max(max_freq, freq.get(i));

        return n - max_freq;
    }
    public static void main(String args[])
    {
        int arr[] = { 10, 3, 4, 4, 2, 4 };
        int n = arr.length;
        System.out.println(noOfMinimumDeletions(arr, n));
    }
}
3

ការវិភាគស្មុគស្មាញសម្រាប់ប្រតិបត្តិការលុបអប្បបរមាដើម្បីធ្វើឱ្យធាតុទាំងអស់នៃអារេដូចគ្នា  

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

អូ (n) កន្លែងណា “ n” គឺជាចំនួនធាតុក្នុងអារេ

សូម​មើល​ផង​ដែរ
ពិនិត្យមើលថាតើអារេផ្ទុកនូវចំនួនគត់ដែលជាប់គ្នាជាមួយច្បាប់ចម្លងដែលបានអនុញ្ញាត

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

អូ (n) កន្លែងណា “ n” គឺជាចំនួនធាតុក្នុងអារេ