د ایکس عناصرو لوی څخه یا مساوي ایکس لیټکوډ حل سره ځانګړي صفونه


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

په ستونزه کې ، "د X عناصرو لوی یا مساوي ایکس سره ځانګړي ځانګړي" ، موږ ته ورکړل شوي سور د غیر منفي عددونو. موږ اړتیا لرو چې یو څه بشپړ X ومومئ چې په سمه توګه د ایکس عناصر شتون لري له هغه څخه په لویه کچه یا له هغه سره په صف کې. که چیرې امکان شتون نلري X چې دا حالت خوښوي ، نو موږ اړتیا لرو -1 تولید.

بېلګه

1 2 3 4
-1
1 3 4 5
3

کړنلاره (د وحشي ځواک)

دا یقیني ده چې که چیرې د حل X شتون ولري ، نو بیا ایکس به تل ځانګړی وي.

ثبوت:

X او Y دوه حلونه په پام کې ونیسئ لکه X! = Y. اجازه راکړئ X <Y. اوس ، د X څخه لوی یا مساوي عناصر شمیر باید X وي ځکه چې موږ یې د حل په توګه ملاحظه کوو. مګر ، د Y> X راهیسې ، دلته د X څخه لوی یا مساوي Y عناصر شتون لري لکه X! = Y. له دې امله زموږ د X حل د حل په توګه غلط دی که نه چې X او Y مساوي وي.

نو ، تل یو ځانګړی حل شتون لري ، که چیرې حل شتون ولري. اوس ، دا هم نتیجه اخیستل کیدی شي چې که X حل وي ، نو بیا د هغې څخه / مساوي لوی عنصرونو شمیر = X ، کوم چې باید د N څخه کم وي ، چیرې چې N = د صف اندازه (د امکان تر کچې د عناصرو شمیر) = ن).

نو ، که چیرې د حل X شتون ولري ، نو دا باید د [1 ، N] حد کې دروغ وي.

موږ د [1 ، N] په لړ کې د هر عدد لپاره کتنه کولی شو که چیرې په صف کې د عناصرو شمیر چې په اندازه کې له کوم عدد څخه لوی یا مساوي وي پخپله ورته انډیجر سره مساوي وي. د مثال په توګه ، سرنی = {1 ، 3 ، 4 ، 5 consider ته پام وکړئ. اوس ، 1 او 2 4 او 3 عناصر لري په ترتیب سره د دوی څخه لوی یا مساوي. د 3 څخه تر مساوي د عناصرو شمیر 3 = 3. نو ، 1 یوازینۍ حل دی. له هغه ځایه چې موږ ټوله ونې تیروو تر څو په لړ کې د هر بشپړتیا لپاره د عناصرو لوی شمیر ومومئ: [XNUMX ، N] ، دا لاره ورو ده.

الګوریتم

  1. د حل کولو لپاره معاینه کولو لپاره له i = 1 څخه i = N څخه یو لوپ چل کړئ:
    • د غټو یا مسایلو د عناصرو شمیر وشمېرئ 'iپه صف کې
      • که شمیره مساوي وي 'i'، بیرته راستنیدنه i
  2. بیرته راګرځی -1;

د ایکس عناصرو لوی څخه یا مساوي ایکس لیټکوډ حل سره د ځانګړي صفونو پلي کول

C ++ برنامه

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

int specialArray(vector <int> &a)
{
    int n = a.size() , counter = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        counter = 0;
        for(int j = 0 ; j < n ; j++)
            if(a[j] >= i)
                counter++;
        if(counter == i)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

جاوا پروګرام

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length , counter = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            counter = 0;
            for(int j = 0 ; j < n ; j++)
                if(a[j] >= i)
                    counter++;
            if(counter == i)
                return i;
        }
        return -1;
    }
}
3

د ایکس عناصرو لوی لوی یا مساوي ایکس لیټکوډ حل سره د ځانګړي صفونو پیچلتیا تحلیل

د وخت پیچلتیا

O (N * N)، N = د صف اندازه. په بدترین حالت کې ، کله چې X = N د حل لاره وي ، موږ O (N * N) پرتله کوو.

د ځای پیچلتیا

O (1). یوازې دوامداره حافظه ځای کارول کیږي.

کړنلاره (مطلوب)

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

اوس ، د عناصرو فریکونسۍ د X څخه لوی یا مساوي د X + څخه د ټولو عنصرونو فریکوینسي د X څخه ډیر. د دې لپاره چې د [1 ، N] په حد کې د هر عنصر لپاره دا ومومئ ، موږ اړتیا لرو د د تعدد فریکوینسي صفاتو لپاره. .

نو ، په صف کې د هر عدد لپاره ، موږ تنظیم کولو ته اړتیا لرو فريکوينسي [i] = فريکوينسي [i] + فريکوينسي [i + 1]، د هرچا لپاره 'i'په لړ کې [N - 1، 1] ، کوم چې به د تړاو د فریکونسۍ صف رامینځته کړي ، د عناصرو شمیر به له لوی یا مساوي سره زیرمه کړي 'i'  as فريکوينسي [i].

اوس ، د کتنې میز له امله ، موږ کولی شو په انټرنیټ [1 ، N] کې په رینج کې د هر ډول عدد لپاره حل وپلټو O (1) وخت دا یوه قضیه ده چیرې چې موږ سپک کول او دروندول په وخت د سمون لپاره حافظه. لدې چې جدول د N اندازې دی ، موږ د حافظې محدودیتونو سره هم اندیښنه نلرو.

 

د ایکس عناصرو لوی څخه یا مساوي ایکس لیټکوډ حل سره ځانګړي صفونه

الګوریتم

  1. پیل کړئ a د فریکونسي د اندازه N کچه، د هر ارزښت په توګه صفر
  2. د هر عنصر لپاره i  په صف کې:
    1. If i > N ، د زیاتوالي فریکوینسي [N]
    2. د زیاتوالي فریکوینسي [i]
  3. د اړونده یو سرنی رامینځته کړئ د فریکونسي لکه:
    1. د هر عنصر پورې اړه لري i = N - 1 ته i = 0
      1. ټولګه فريکوينسي [i] = فريکوينسي [i] + فریکوینسي [i + 1]
  4. له څخه یوه کړۍ چلول i = 1 ته i = ن
    1. If i == فریکوینسي [i] ، بیرته i
  5. راستنیدنه -1

د ایکس عناصرو لوی څخه یا مساوي ایکس لیټکوډ حل سره د ځانګړي صفونو پلي کول

C ++ برنامه

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

int specialArray(vector<int>& a)
{
    int n = a.size();
    vector <int> frequency(n + 1 , 0);
    for(int i = 0 ; i < n ; i++)
        if(a[i] > n)
            frequency[n]++;
        else
            frequency[a[i]]++;

    for(int i = n - 1 ; i >= 0 ; i--)
        frequency[i] += frequency[i + 1];

    for(int i = 0 ; i <= n ; i++)
        if(frequency[i] == i)
            return i;

    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 4 , 5};
    cout << specialArray(a) << '\n';
}

جاوا پروګرام

class special_array
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 4 , 5};
        System.out.println(specialArray(a));
    }

    static int specialArray(int[] a)
    {
        int n = a.length;
        int[] frequency = new int[n + 1];
        for(int i = 0 ; i < n ; i++)
            frequency[i] = 0;

        for(int i = 0 ; i < n ; i++)
            if(a[i] > n)
                frequency[n]++;
            else
                frequency[a[i]]++;

        for(int i = n - 1 ; i >= 0 ; i--)
            frequency[i] += frequency[i + 1];

        for(int i = 0 ; i <= n ; i++)
            if(frequency[i] == i)
                return i;

        return -1;
    }
}
3

د ایکس عناصرو لوی لوی یا مساوي ایکس لیټکوډ حل سره د ځانګړي صفونو پیچلتیا تحلیل

د وخت پیچلتیا

O (N)، N = د صف اندازه. موږ کولی شو په O (1) وخت کې د هر ډول عدد لپاره وګورو ، نو په بدترین حالت کې موږ د O (N) وخت کاروو.

د ځای پیچلتیا

O (N). د خطي حافظې ځای د فریکونسۍ ذخیره کولو لپاره کارول کیږي.