د اندازې ورک شوي عناصر ومومئ


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي دهلي ګریورینج LinkedIn نګارو اوپرا Synopsys
هاش لارسن او توابرو ترتیب کول

ستونزه د سلسلې ورک شوي عناصر ومومئ "په ګوته کوي چې تاسو ته ورکړل شوي سور په ځانګړي حد کې د ځانګړو عناصرو او د حد او ټیټ کچې په توګه ورکړل شوي. ټول د ورک شوي عناصر په لړ کې ومومئ کوم چې په صف کې شتون نلري. محصول باید په ترتیب شوي ترتیب کې وي.

بېلګه

د اندازې ورک شوي عناصر ومومئ

arr[] = [1, 3, 5, 7, 8, 9]

low=1 high = 10
2, 4, 6, 10

تشریح

دا د صف په مینځ کې ورکې شوي شمیرې دي چې د ټیټ او لوړې کچې په توګه ورکول کیږي ، 1 او 10.

arr[] = [2, 3, 7, 8]

low=1 high = 9
1, 4, 5, 6, 9

تشریح

دا د صف په مینځ کې ورکې شوي شمیرې دي چې د ټیټ او لوړې کچې په توګه ورکول کیږي ، 1 او 10.

الګوریتم

  1. اعلامیه a ټولګه.
  2. صف ځنډول او ټول عناصر په سیټ کې کېږدئ.
  3. پداسې حال کې چې "i" د ټیټ سره برابر دی او "i" له برابر سره لوړ دی.
    • که چیرې سیټ "i" ونه لري.
      • 'زه' چاپ کړئ.

تشریح

موږ ته د ستونزې بیان ورکړل شوی چې غوښتنه یې کړې چې په ورکړل شوي حد کې دننه په صف کې ټول ورک شوي عناصر ومومئ ځکه چې ټیټ او لوړ دي. د دې د حل لپاره موږ به سیټ وکاروو او د ورکړل شوي صفونو سیټ کې به ارزښتونه زیرمو ته ځو. موږ ته د ټیټ او لوړ کچې اندازه ورکړل شوې ، موږ باید ټول عناصر په ټیټ او لوړ کې دننه چاپ کړو.

د دې ترتیب ترلاسه کولو لپاره موږ دمخه په سایټ کې د صف عناصر ذخیره کوو. موږ اړتیا لرو چې د 'i' ټیټ ټیټ پیل کړئ. موږ لاپ چلوو تر هغه وخته چې د 'i' ارزښت لوړی شي. بیا چیک کړئ که سیټ د 'i' ارزښت نه لري نو بیا 'i' چاپ کړئ. له همدې امله موږ به ټول هغه عناصر ترلاسه کړو چې په ورکړل شوي حد کې دننه له صف څخه ورک دي. راځئ چې یو مثال په پام کې ونیسو.

تیر [] = {2 ، 3 ، 7 ، 8} ټیټ = 1 ، لوړ = 9

موږ اړتیا لرو چې د ارې تیر کړو او د صفونو ټول عناصر سیټ ته واړوو. زموږ سیټ به شي

سیټ = [2,3,7,8،XNUMX،XNUMX،XNUMX]

په لوپ کې زه ټیټ ته ابتداء کوم او لوپ تر لوړې پورې ځي ، پدې معنی چې 'i' د ټیټ = 1 او لوړې = 9 سره مساوي دی.

i = 1 ، که چیرې سیټ i ونه لري ، 1 چاپ کوي

[1]

i = 2 ، سیټ '2' ارزښت لري او هیڅ نه کوي.

i = 3 ، سیټ '3' ارزښت لري او هیڅ نه کوي.

i = 4 ، که چیرې سیټ i ونه لري ، 4 چاپ کوي

[1، 4]

i = 5 ، که چیرې سیټ i ونه لري ، 5 چاپ کوي

[1، 4، 5]

i = 6 ، که چیرې سیټ i ونه لري ، 6 چاپ کوي

[1 ، 4 ، 5 ، 6]

i = 7 ، سیټ '7' ارزښت لري او هیڅ نه کوي.

i = 8 ، سیټ '8' ارزښت لري او هیڅ نه کوي.

i = 9 ، که چیرې سیټ i ونه لري ، 1 چاپ کوي

[1 ، 4 ، 5 ، 6 ، 9]

زموږ محصول به شي: [1 ، 4 ، 5 ، 6 ، 9]

کوډ

د لړۍ د ورک عناصر موندلو لپاره C ++ کوډ

#include <unordered_set>
#include<iostream>

using namespace std;

void getMissingElements(int arr[], int n, int low, int high)
{
    unordered_set<int> myset;
    for (int i = 0; i < n; i++)
        myset.insert(arr[i]);

    for (int x = low; x <= high; x++)
        if (myset.find(x) == myset.end())
            cout << x << " ";
}
int main()
{
    int arr[] = { 2,3,7,8 };
    int low = 1, high = 9;
    int n = sizeof(arr) / sizeof(arr[0]);
    getMissingElements(arr, n, low, high);
    return 0;
}
1 4 5 6 9

د رینج ورک شوي عناصر موندلو لپاره جاوا کوډ

import java.util.HashSet;

class RangeMissingElements
{
    public static void getMissingElements(int arr[], int low, int high)
    {
        HashSet<Integer> myset = new HashSet<>();

        for (int i = 0; i < arr.length; i++)
        {
            myset.add(arr[i]);
        }

        for (int i = low; i <= high; i++)
        {
            if (!myset.contains(i))
            {
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,7,8};
        int low = 1, high = 9;
        getMissingElements(arr, low, high);
    }
}
1 4 5 6 9

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

د وخت پیچلتیا

O (n + (لوړ - ټیټ + 1)) هلته "n" په صف کې د موجودو عناصرو شمیر دی ، "لوړ" او "ټیټ" ورکړل شوی ننوت دی.

د ځای پیچلتیا

O (n) ، په خورا بد حالت کې ، که ټول عناصر توپیر ولري. موږ به ټول عناصر ذخیره کړو. پدې توګه د الګوریتم رامینځته کول لیکري وخت ته اړتیا لري.