range တစ်ခု၏ element အားလုံး array ထဲတွင်ရှိနေရန်အတွက်ထည့်ရန် Element များဖြစ်သည်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် GreyOrange Kuliza Snapdeal မြတ်နိုး Teradata Times ကိုအင်တာနက်
အခင်းအကျင်း hash တားဆီးခြင်း sorting

ပြProbleနာဖော်ပြချက်

“ element တွေထပ်တိုးဖို့ range တစ်ခုရဲ့ element အားလုံး array ထဲမှာရှိနေမယ်” ဟုသင်ကိန်းတန်းတစ်ခုပေးသည်ဟုဖော်ပြသည်။ အဆိုပါပြstatementနာကြေညာချက်က element အားလုံးသည်အကွာအဝေး [X, Y] အားလုံးပါ ၀ င်သော array တွင်အနည်းဆုံးတစ်ကြိမ်ပါ ၀ င်စေရန် array ထဲတွင်ထည့်သွင်းမည့် element အရေအတွက်ကိုရှာဖွေရန်တောင်းသည်။ X နှင့် Y တို့သည်အနိမ့်ဆုံးနှင့်အမြင့်ဆုံးနံပါတ်များဖြစ်သည်။

နမူနာ

arr[] = {4,5,7,9,11}
3

ရှင်းလင်းချက် - X and Y သည် 4 နှင့် 11 (အနည်းဆုံးနှင့်အများဆုံးနံပါတ်များအသီးသီးဖြစ်သည်) ဖြစ်သည်။ ဤနံပါတ်များအတွင်းတွင် ၃၊ ၆၊ ၈ နှင့် ၁၀ တို့သာပျောက်ဆုံးနေသည်။

range တစ်ခု၏ element အားလုံး array ထဲတွင်ရှိနေရန်အတွက်ထည့်ရန် Element များဖြစ်သည်

arr[] = {2,4,6,7}
2

ရှင်းလင်းချက် - X and Y သည် ၂ နှင့် ၇ (အနည်းဆုံးနှင့်အများဆုံးနံပါတ်များအသီးသီးဖြစ်သည်) ဖြစ်သည်။ ဤနံပါတ်များအတွင်းတွင် ၂ နှင့် ၃ ခုသာပျောက်ဆုံးနေသည်။

Element များထပ်ပေါင်းထည့်ရန်ရှာရန် Algorithm သည်အကွာအဝေး၏ element အားလုံးသည် array ထဲတွင်ရှိသည်

1. Declare a Set.
2. Set output to 0, minValue to the maximum value of integer and maxValue to the minimum value of an integer.
3. Traverse the array and put all the values into the set and simultaneously find out the maximum and the minimum number of an array and store it to the maxValue and minValue respectively.
4. Traverse the array again, from minValue to maxValue.
5. Check if the map doesn’t contain any of the elements in traversal, then, increase the count of output.
6. Return output.

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

ကျနော်တို့အနေနဲ့ပြီ ကိန်း array ။ ပြနာမှာ array ထဲတွင်ထည့်သွင်းမည့် element အရေအတွက်ကိုရှာဖွေရန်ဖြစ်သည်။ ထို့ကြောင့် element အားလုံးသည် array နှင့်အနိမ့်ဆုံးနံပါတ်များအကွာအဝေးတွင်ရှိနေရန်မည်သည့် element မှအနည်းဆုံးတစ်ကြိမ်မဖြစ်ပေါ်စေရန်ဖြစ်သည်။

Set ကြေငြာပါ၊ သတ်မှတ်ရန်မှာကွဲပြားသောဒြပ်စင်များကိုတစ်ကြိမ်သာသိုလှောင်ရန်ပိုင်ဆိုင်မှုရှိသည်။ ဆိုလိုသည်မှာ၎င်းသည် common element များကိုဖယ်ရှားပြီးကွဲပြားသော element များကိုသာသိုလှောင်ခြင်းဖြစ်သည်။ ဒါကြောင့်ငါတို့ကဒီကိစ္စကိုကိုင်တွယ်နိုင်လိမ့်မယ်။ ယခုကျွန်ုပ်တို့သည် array element များအားလုံးကို set ထဲသို့ထည့်တော့မည်ဖြစ်သည်။ တစ်ပြိုင်နက်တည်းကျွန်ုပ်တို့သည်အမြင့်ဆုံးနှင့်အနိမ့်ဆုံး element ကိုရှာဖွေတွေ့ရှိလိမ့်မည်။ max နှင့် min ကိုရှာရန်အပိုသွားရန်မလိုပါ။ ပြီးနောက်ရှိသမျှတို့, ကျနော်တို့အကွာအဝေးအတွင်းပျောက်ဆုံးနေ Element တွေကို၏အရေအတွက်ကိုရှာဖွေရန်လိုအပ်သည်။ ဒီတော့ဂဏန်းတွေကိုရေတွက်ဖို့လိုတယ်။ ပြီးတော့ငါတို့ကိန်းဂဏန်းတွေကိုသူတို့ဘာသာမကိုင်တွယ်ရဘူး။

ယခုကျွန်ုပ်တို့သည် array အတွင်းအနိမ့်ဆုံးတန်ဖိုးမှအမြင့်ဆုံးတန်ဖိုးတစ်ခုအထိစတင်ဖြတ်သန်းသွားမည်ဖြစ်သည်။ ဒါကငါတို့လိုအပ်တဲ့တစ်ခုတည်းသောအကွာအဝေးပါ။ ကျွန်ုပ်တို့သည်အကွာအဝေးအတွင်းရှိနံပါတ်တစ်ခုစီကိုရွေးပြီးအစုတွင်ထိုအကွာအဝေး၏တန်ဖိုးမရှိပါကစစ်ဆေးလိမ့်မည်။ အကယ်၍ set တွင်လက်ရှိ range တန်ဖိုးမပါရှိပါက output output ကိုတိုးမြှင့်သွားမည်။ ပြီးတော့အစုတစ်ခုမှာတန်ဖိုးအတိုင်းအတာတစ်ခုမှမရှိတဲ့အခါတိုင်း output ရဲ့တန်ဖိုးကို ၁ နဲ့တိုးပေးမယ်။ အထက်ဖော်ပြပါကုဒ်မှာအနည်းဆုံး ၄ ဖြစ်ပြီးအမြင့်ဆုံးသည် ၁၁ နှင့် ၆.၈ နှင့် ၁၀ ကြားတွင်အကွာအဝေးအတွင်း (၄,၁၁) အတွင်းပျောက်ဆုံးနေသည်ဆိုပါက၎င်းဒြပ်စင်များကိုခင်းကျင်းပြသထားခြင်းမရှိသည့်အတွက်၎င်းအရေအတွက်ကိုရေတွက်လိမ့်မည်။ နောက်ဆုံးတော့အဲ့ဒီ output ကိုကျွန်တော်တို့ပြန်ပေးလိမ့်မယ်။

ကုဒ်

C ++ ကုဒ်သည်ဒြပ်ပေါင်းများကိုထည့်သွင်းရန်ရှာရန်အတွက်အကွာအဝေးတစ်ခု၏ဒြပ်ထုအားလုံးသည် array ထဲတွင်ရှိသည်

#include<iostream>
#include<unordered_set>

using namespace std;

int getCountMissingNumber(int arr[], int n)
{
    unordered_set<int> SET;
    int output = 0;
    int maxValue = INT_MIN;
    int minValue = INT_MAX;

    for (int i = 0; i < n; i++)
    {
        SET.insert(arr[i]);
        if (arr[i] < minValue)
            minValue = arr[i];
        if (arr[i] > maxValue)
            maxValue = arr[i];
    }
    for (int a = minValue; a <= maxValue; a++)
    {
        if (SET.find(a) == SET.end())
        {
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {4,5,7,9,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getCountMissingNumber(arr, n);
    return 0;
}
3

Java ကုဒ်များသည် Element များထပ်ပေါင်းထည့်ရန်ရှာရန်အကွာအဝေး၏အစိတ်အပိုင်းအားလုံးသည် array ထဲတွင်ရှိသည်

import java.util.HashSet;

class NumberBwRange
{
    public static int getCountMissingNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<>();
        int output = 0;
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
            if (arr[i] < minValue)
                minValue = arr[i];
            if (arr[i] > maxValue)
                maxValue = arr[i];
        }

        for (int i = minValue; i <= maxValue; i++)
            if (!SET.contains(i))
                output++;
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 4,5,7,9,11 };
        int n = arr.length;
        System.out.println(getCountMissingNumber(arr, n));
    }
}
3

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

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

အို (အများဆုံး - min + 1) ဘယ်မှာ “ max” နှင့် “ min” အဆိုပါများမှာ အများဆုံး နှင့် အနည်းဆုံး အဆိုပါခင်းကျင်း၏တန်ဖိုး။ ကျနော်တို့နိမ့်ဆုံးဒြပ်စင်ကနေအများဆုံးဒြပ်စင်မှဖြတ်သန်းကတည်းက။ ဒါကြောင့်အဆိုးဆုံးအခြေအနေမှာဒီတန်ဖိုးဟာ N element တွေထက်ကျော်လွန်သွားနိုင်တယ်။ ထို့ကြောင့် max-min + 1 သည် N. ထက်ကြီးသောကြောင့်အချိန်ရှုပ်ထွေးမှုသည် O (max-min + 1) ဖြစ်သောကြောင့် max သည်အများဆုံးဒြပ်စင်ကိုရည်ညွှန်းပြီး min သည်အနိမ့်ဆုံး element ကိုဆိုလိုသည်။

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

အို (N) ဘယ်မှာ "N" သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ ကျွန်ုပ်တို့သည် N element များသာသိုလှောင်ထားခြင်းကြောင့် algorithm တွင် linear space ရှုပ်ထွေးမှုရှိသည်။