عنصرونه باید اضافه شي نو د کچې ټول عناصر په صف کې شتون لري


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ګریورینج کولیزا سنیپډیل Synopsys Teradata ټایمز انټرنیټ
پیشه هاش ځورول ترتیب کول

ستونزه بیان

"عنصرونه باید اضافه شي نو د کچې ټول عناصر په صف کې شتون لري" په ګوته کوي چې تاسو ته دقیق صفونه درکول کیږي. د ستونزې بیان غوښتنه کوي چې په عناصر کې د شاملولو لپاره د عناصرو شمیره ومومئ ترڅو ټول عناصر [X، Y] په حد کې شامل وي لږ تر لږه یوځل یوځل په صف کې. X او Y په ترتیب سره د یو صف لږترلږه او اعظمي شمیرې دي.

بېلګه

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

توضیحي: X او Y 4 او 11 دي (په ترتیب سره لږترلږه او اعظمي شمیرې) ، د دې شمیرو په لړ کې ، یوازې 3 د 6 ، 8 او 10 ورک دي.

عنصرونه باید اضافه شي نو د کچې ټول عناصر په صف کې شتون لري

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

توضیحات: X او Y 2 او 7 دي (په ترتیب سره لږترلږه او اعظمي شمیرې) ، د دې شمیرو په لړ کې ، یوازې 2 د 3 او 5 ورک دي.

د اضافو کیدو لپاره د عناصرو موندلو لپاره الګوریتم نو ترڅو چې د لړۍ ټول عناصر په صف کې شتون ولري

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.

تشریح

موږ یو ضمیمه صف. ستونزه په صف کې د اضافه کیدو لپاره د عناصرو شمیر معلومول دي. نو ځکه چې ټول عناصر د یو صف د حد او حد اقل حد کې دي نو هیڅ عناصر باید لږترلږه یوځل واقع نشي.

سیټ اعلان کړئ ، سیټ یوازې یو ځل د ځانګړو عناصرو ذخیره کولو لپاره ملکیت لري. پدې معنی چې دا عام عناصر لرې کوي او یوازې ځانګړي عنصرونه ذخیره کوي. نو موږ به وکولی شو دا قضیه اداره کړو. اوس موږ سیټ کې د ټولو عناصرو عناصر داخل کوو. په ورته وخت کې به موږ اعظمي او لږترلږه عنصر ومومو. نو ځکه چې موږ اړتیا نلرو اضافي ټروریسټال رامینځته کړئ ترڅو د اعظمي اوقیقې موندلو لپاره. په هرصورت ، موږ یوازې دې ته اړتیا لرو چې په حد کې د ورک شوي عناصرو شمیر معلوم کړو. نو یوازې د شمیرلو لپاره اړتیا شتون لري. او موږ اړتیا نلرو چې پخپله د شمیرو سره معامله وکړو.

اوس ، موږ به په صف کې تیر شو چې په صف کې د لږترلږه ارزښت څخه د سرنی اعظمي ارزښت ته. ځکه چې دا یوازینی حد دی چې موږ ورته اړتیا لرو. موږ به هره شمیره په حد کې واخلو او وګورو چې آیا سیټ د دې حد ارزښت نلري. که سیټ دا اوسني رینج ارزښت ونه لري ، نو بیا موږ د محصول شمیره لوړه کوو. او هر ځل به موږ د 1 لخوا د محصول ارزښت ډیروو کله چې موږ په سیټ کې د سلسلې ارزښت شتون نلرو. لکه څنګه چې په یاد شوي کوډ کې لږترلږه 4 دي او اعظمي یې 11 دي او د 6,8،10 او 4,11 ترمینځ په مینځ کې ورک شوي (XNUMX،XNUMX) ، هم دا عناصر په صف کې شتون نلري نو د عناصرو شمیر به یې شمیرل کیږي. او په نهایت کې ، موږ به دا محصول بیرته راولو.

کوډ

C ++ کوډ ترڅو اضافه کولو لپاره عناصر ومومئ ترڅو د لړۍ ټول عناصر په صف کې شتون ولري

#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

د اضافو کیدو لپاره د عنصرونو موندلو لپاره جاوا کوډ نو ترڅو د لړۍ ټول عناصر په صف کې شتون ولري

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

د پیچلتیا تحلیل

د وخت پیچلتیا

O (اعظمي - دقیقه + 1) هلته "اعظمي" او "من" دی اعظمي او لږ تر لږه د صف ارزښت. له هغه وخته چې موږ د لږترلږه عنصر څخه اعظمي عنصر ته وګرځو. له همدې امله په بد حالت کې دا ارزښت ممکن د N عناصرو څخه ډیر شي. نو ، ځکه چې اعظمي حد + 1 ممکن د N څخه لوی وي. د وخت پیچلتیا O ده (max-min + 1) چیرې چیرې اعظمي اعظمي عنصر منعکس کوي ، او min لږترلږه عنصر په نښه کوي.

د ځای پیچلتیا

O (N) هلته "N" په صف کې د عناصرو شمیر دی. له هغه وخته چې موږ یوازې د N عناصرو ذخیره کوو د الګوریتم خطي خلا پیچلتیا لري.