အမြင့်ဆုံးနှင့်အနည်းဆုံးကြိမ်နှုန်းတစ်ခုအကြားကွာခြားချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Citadel fab လေးကစ် Roblox တက်စလာ
အခင်းအကျင်း hash sorting

ပြarrayနာ“ အမြင့်ဆုံးနှင့်အနိမ့်ဆုံးကြိမ်နှုန်းများကိုခင်းကျင်းခြင်းအကြားခြားနားချက်” တွင်သင်၌ရှိသည်ဟုဆိုထားသည် ကိန်း အခင်းအကျင်း။ အဆိုပါပြstatementနာကြေညာချက်အမြင့်ဆုံးကြိမ်နှုန်းနှင့်တစ်ခုခင်းကျင်းနှစ်ခုကွဲပြားနံပါတ်များ၏နိမ့်ဆုံးကြိမ်နှုန်းအကြားအများဆုံးကွာခြားချက်ထွက်ရှာတွေ့မှမေးတယ်။

နမူနာ

အမြင့်ဆုံးနှင့်အနည်းဆုံးကြိမ်နှုန်းတစ်ခုအကြားကွာခြားချက်

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

ရှင်းလင်းချက်

ကြိမ်နှုန်း 1 → 3 (အမြင့်ဆုံးကြိမ်နှုန်း)

ကြိမ်နှုန်း 5 → 1 (အနိမ့်ဆုံးကြိမ်နှုန်း)

arr[] = {5, 4, 5, 5, 5, 3, 4 }
3

ရှင်းလင်းချက်

ကြိမ်နှုန်း 5 → 4 (အမြင့်ဆုံးကြိမ်နှုန်း)

ကြိမ်နှုန်း 3 → 1 (အနိမ့်ဆုံးကြိမ်နှုန်း)

algorithm

  1. a) ကြေညာပါ ေျမပုုံ.
  2. array element တစ်ခု၏ကြိမ်နှုန်းကိုသိမ်းဆည်းပါ။
  3. အစုံ maxfreq 0 နဲ့ နင် သို့ n.
  4. မြေပုံကိုဖြတ်သန်းပါ
    1. မြေပုံရှိ maxfreq နှင့်ကြိမ်နှုန်းအကြားရှိအများဆုံးတန်ဖိုးကိုရှာဖွေပြီး၎င်းကို maxfreq တွင်သိမ်းထားပါ။
    2. minfreq နှင့်မြေပုံရှိကြိမ်နှုန်းအကြားအနည်းဆုံးတန်ဖိုးကိုရှာပြီး minfreq တွင်သိမ်းထားပါ။
  5. (maxfreq-minfreq) သို့ပြန်သွားပါ။

ရှင်းလင်းချက်

ကျနော်တို့ကိန်းတစ်ခုခင်းကျင်းရှိသည်။ ကျွန်ုပ်တို့၏တာ ၀ န်သည်အမြင့်ဆုံးဖြစ်ပျက်မှုနှင့်အနိမ့်ဆုံးဖြစ်ပျက်မှုနှစ်ခုအကြားအမြင့်ဆုံးကွာခြားမှုကိုရှာဖွေရန်ဖြစ်သည်။ ငါတို့သုံးမယ် ဟေး။ Hashing သည်ဤမေးခွန်းကိုဖြေရှင်းရန်ထိရောက်သောနည်းလမ်းဖြစ်သည်။ ကျွန်ုပ်တို့သည်မြေပုံတစ်ခုကိုကြေငြာရန်နှင့် array ဒြပ်စင်တစ်ခုစီ၏ကြိမ်နှုန်းကိုရေတွက်ရန်နှင့်ကြိမ်နှုန်းများနှင့်အတူမြေပုံထဲကိုတစ်ပြိုင်တည်းသိုလှောင်ရန်သွားမည်။

ပြီးရင်တန်ဖိုးကိုသတ်မှတ်ပါမယ် maxfreq 0 နဲ့ နင် မည်သည့်ဒြပ်စင်မှပေးထားသောခင်းကျင်း၏အရွယ်ထက်ပိုသောကြိမ်နှုန်းကိုမရှိသောကြောင့် n မှဆိုလိုသည်။ ကျွန်ုပ်တို့သည်မြေပုံကိုဖြတ်သန်းသွားပြီးဒြပ်စင်တစ်ခုစီကိုတစ်ခုချင်းစီကောက်ယူကာ၎င်းသည်အမြင့်ဆုံးသို့မဟုတ်အနိမ့်ဆုံးကြိမ်နှုန်းရှိမရှိစစ်ဆေးမည်ဖြစ်သည် အမြင့်ဆုံးကြိမ်နှုန်းကိုမတူညီသော variable တစ်ခုနှင့်အနည်းဆုံးကြိမ်နှုန်းကိုမတူညီသော variable သို့ခွဲခြားပါ။ ကျွန်ုပ်တို့သည်အများဆုံးကြိမ်နှုန်းနှင့်အနိမ့်ဆုံးကြိမ်နှုန်းအကြားခြားနားချက်ကိုပြန်ပို့ရန်လိုအပ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် (maxfreq-minfreq) ပြန်လာမည်။

ဥပမာတစ်ခုယူကြစို့။

နမူနာ

arr [] = {၁၊ ၂၊ ၃၊ ၁၊ ၅၊ ၂၊ ၃၊ ၁}

ပထမ ဦး ဆုံး array ကိုဖြတ်သန်းသောအခါ element နှင့် ၄ င်းတို့၏ဖြစ်ပျက်မှုများကိုမြေပုံထဲသို့ထည့်ပြီးဖြတ်သန်းပြီးနောက်မြေပုံသည် -

မြေပုံ - {၁: ၃၊ ၂: ၂၊ ၃: ၂၊ ၅: ၁}

အခုဆိုရင်ငါတို့မြေပုံထဲမှာဒြပ်စင်တစ်ခုချင်းစီရဲ့အဖြစ်အပျက်တွေရှိနေပြီ၊ မြေပုံကိုဖြတ်ပြီးသွားမယ်၊ မြေပုံထဲက element တစ်ခုချင်းစီကိုကောက်ယူပြီးသူတို့ရဲ့ကြိမ်နှုန်းကိုစစ်ဆေးတယ်၊ ဒီပမာဏကသာမာန်ကြိမ်နှုန်း (သို့) maxfreq အမြင့်ဆုံးဖြစ်ပြီး၊ minfreq နှင့်၎င်းကို maxfreq နှင့် minfreq သို့အသီးသီးသိုထားပါ။

  • ၁: ၃ →

3 maxfreq ထက်သာ။ ကြီးမြတ်သည်, ဒါကြောင့် maxfreq = 3

3 minfreq ထက်သေးငယ်တယ်၊ ဒါကြောင့် minfreq = 3

  • ၁: ၃ →

maxfreq သည် ၂ ထက်ကြီးသည်၊ ထို့ကြောင့် maxfreq = 2

2 minfreq ထက်သေးငယ်တယ်၊ ဒါကြောင့် minfreq = 2

  • ၁: ၃ →

maxfreq သည် ၂ ထက်ကြီးသည်၊ ထို့ကြောင့် maxfreq = 2

အဘယ်အရာကိုမျှ minfreq, minfreq = 2 အတွက်ပြောင်းလဲသွားတယ်ဖြစ်ပါတယ်

  • ၁: ၃ →

maxfreq သည် ၂ ထက်ကြီးသည်၊ ထို့ကြောင့် maxfreq = 1

1 minfreq ထက်သေးငယ်တယ်၊ ဒါကြောင့် minfreq = 1

တဖန်ငါတို့ maxfreq-minfreq → (3-1) = 2 အကြားခြားနားချက်ကိုပြန်လာပါလိမ့်မယ်။

ကုဒ်

C ++ ကုဒ်သည်အမြင့်ဆုံးနှင့်အနည်းဆုံးကြိမ်နှုန်းအကြားကွာခြားမှုကိုရှာဖွေရန်ဖြစ်သည်

#include<iostream>
#include<unordered_map>

using namespace std;

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

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

အမြင့်ဆုံးနှင့်အနည်းဆုံးကြိမ်နှုန်းများအကြားကွာခြားချက်ကိုရှာဖွေရန် Java ကုဒ်ဖြစ်သည်

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        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);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ဤနေရာတွင်ကျွန်ုပ်တို့သည်သူတို့၏ကြိမ်နှုန်းများကိုခြေရာခံသည့် array ၏ element များကိုရိုးရှင်းစွာဖြတ်သန်းသွားသည်။ ဤအရာအားလုံးသည်အို (N) အချိန်သာကျပါသည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ အများဆုံးမှာကျွန်ုပ်တို့အားလုံးသည်ကွဲပြားပါက n element များကိုသိမ်းဆည်းနိုင်သည်။ အဆိုပါအာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။