ထက်ကြီးသောသို့မဟုတ်တူညီသော X Leetcode Solution ရှိသော X Element များပါ ၀ င်သည့်အထူး Array


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Google
အခင်းအကျင်း တားဆီးခြင်း

ထိုပြနာတွင်“ X ထက်ပိုမိုကြီးသောသို့မဟုတ်တန်းတူညီမျှသည့် X element များ၏အထူး Array” ကိုကျွန်ုပ်တို့အားပေးထားသည် အခင်းအကျင်း Non- အနုတ်ကိန်း၏။ ကိန်းသေတစ်ခုအနေနှင့်၎င်းထက်ကြီးသောသို့မဟုတ်တန်းတူညီမျှမှုရှိသော X element များအတိအကျရှိသောကိန်းရှင်အချို့ကိုရှာဖွေရန်လိုအပ်သည်။ ဒီအခြေအနေနဲ့ကိုက်ညီမယ့် ​​X မဖြစ်နိုင်ရင် output -1 ကိုထုတ်ဖို့လိုတယ်။

မာတိကာ

နမူနာ

1 2 3 4
-1
1 3 4 5
3

ချဉ်းကပ်နည်း (Brute Force)

အကယ်၍ အဖြေတစ်ခု X ရှိခဲ့လျှင်၊ X သည်အမြဲတမ်းထူးခြားလိမ့်မည်။

အထောက်အထား:

X! = Y. ဒီဟာကို X နှင့် Y လို့ခေါ်တဲ့အဖြေနှစ်ခုရှိတယ်စဉ်းစားကြည့်ပါ။ X <Y. ဆိုပါစို့။ အခုဆိုရင် X ထက်ကြီးတဲ့ဒါမှမဟုတ်ညီမျှတဲ့ element အရေအတွက်က X ဖြစ်သင့်တယ်။ သို့သော် Y> X ကတည်းက Y ထက် ပို၍ ကြီးသော (သို့) ညီမျှသော Y elementals သည်ထိုကဲ့သို့သော X! = Y. ထို့ကြောင့် X နှင့် Y သည်တန်းတူမဟုတ်ပါက X ၏အဖြေသည်မှားသည်။

ထို့ကြောင့်အဖြေတစ်ခုရှိပါကထူးခြားသောဖြေရှင်းနည်းတစ်ခုအမြဲရှိသည်။ ယခုတွင်မူ X ကအဖြေတစ်ခုဖြစ်လျှင်၎င်းသည်ညီမျှသော / ညီမျှသောဒြပ်စင်အရေအတွက် = X ဖြစ်သည်။ ၎င်းသည် N ထက်နည်းသင့်ပြီး၎င်းသည် N = ခင်းကျင်း၏အရွယ်အစား (ဖြစ်နိုင်သမျှအများဆုံးဒြပ်စင်အရေအတွက်အနေဖြင့်) ဖြစ်သည်။ = N ကို) ။

ဒီတော့ အကယ်၍ အဖြေ X ရှိတယ်ဆိုလျှင်၊ အကွာအဝေး [1, N ကို] ၌အိပ်ရကြမည်။

အကွာအဝေးရှိမည်သည့်ကိန်းထက်မဆိုပိုမိုကြီးမားသို့မဟုတ်ညီမျှသည်ဆိုပါကအကွာအဝေး [1, N] အတွင်းရှိကိန်းအားလုံးကိုစစ်ဆေးနိုင်သည်။ ဥပမာ Array = {1, 3, 4, 5} ကိုစဉ်းစားပါ။ အခုဆိုရင် 1 နဲ့ 2 မှာ 4 နဲ့ 3 element တွေရှိတယ်။ သူတို့က array ထဲမှာသူတို့ထက်ကြီးတဲ့ (သို့) ညီမျှတယ်။ ထက် ၃ / ၃ ထက်ကြီးသောဒြပ်စင်အရေအတွက်ထို့ကြောင့် ၃ သည်တစ်ခုတည်းသောဖြေရှင်းနည်းဖြစ်သည်။ သစ်ပင်တစ်ခုလုံးကိုကျွန်ုပ်တို့ဖြတ်သန်းသွားသောကြောင့်အကွာအဝေးအတွင်းရှိကိန်းအားလုံးထက်ပိုမိုသောဒြပ်စင်အရေအတွက်ကိုရှာဖွေသောကြောင့် [3, N] ဤချဉ်းကပ်မှုသည်နှေးကွေးသည်။

algorithm

  1. ဖြေရှင်းချက်ကိုစစ်ဆေးရန် i = 1 မှ i = N မှကွင်းဆက်တစ်ခုကိုဖွင့်ပါ။
    • 'ထက်ကြီးသောသို့မဟုတ်ညီမျှသော element များ၏နံပါတ်ကိုရေတွက်ပါ။i'' အခင်းကျင်း၌တည်၏
      • အကယ်၍ အရေအတွက်က 'ညီမျှတယ်ဆိုရင်'i'ငါပြန်လာ
  2. ပြန်လာ -1;

အထူး Array အထူးပြု X ထက် ပို၍ ကြီးသောသို့မဟုတ်တူညီသော X Leetcode Solution ဖြင့်အသုံးပြုခြင်း

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';
}

Java အစီအစဉ်

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

အထူးပြု Array ကိုရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်းထက် ပို၍ ကြီးသောသို့မဟုတ် Equal X Leetcode Solution ဖြင့်အသုံးပြုခြင်း

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

အို (N * N), N ကို = ခင်းကျင်း၏အရွယ်အစား။ အဆိုးဆုံးအနေဖြင့် X = N သည်အဖြေဖြစ်သည့်အခါ O (N * N) ကိုနှိုင်းယှဉ်သည်။

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

အို (၁)။ စဉ်ဆက်မပြတ်မှတ်ဉာဏ်နေရာသာအသုံးပြုသည်။

ချဉ်းကပ်မှု (အကောင်းဆုံး)

element တစ်ခု၏ဖြစ်ပျက်မှုအရေအတွက်ကို table တစ်ခုဖြင့် သုံး၍ သိမ်းနိုင်သည်။ သတိပြုရန်မှာ N ထက်ကြီးသောတန်ဖိုးရှိသောမည်သည့်ဒြပ်စင်အတွက်မဆို၎င်းသည် N အားတန်ဖိုးရှိသော element တစ်ခုအဖြစ် သတ်မှတ်၍ ဖြစ်သည်။ အမြင့်ဆုံးတန်ဖိုးသည် N. ဖြစ်နိုင်သောကြောင့်

ယခု X ထက်ကြီးသောသို့မဟုတ်ညီမျှသော element များ၏ကြိမ်နှုန်းသည် X = ကြိမ်နှုန်းထက် X ထက်ပိုသောဒြပ်စင်၏ကြိမ်နှုန်း၏ကြိမ်နှုန်းဖြစ်သည်။ အကွာအဝေးရှိဒြပ်စင်တိုင်းအတွက်ဤရှာဖွေရန်အတွက် [1, N] တွင်ကျွန်ုပ်တို့သည် suffix frequency array လိုအပ်သည်။ ။

ဒီတော့ array ထဲမှာရှိတဲ့ကိန်းတစ်ခုစီအတွက်ကျွန်တော်တို့သတ်မှတ်ထားရမယ် ကြိမ်နှုန်း [i] = ကြိမ်နှုန်း [i] + ကြိမ်နှုန်း [i + 1]တိုင်းအတွက်i'အကွာအဝေး [N - ၁, ၁] သည်၊ ထက်ပိုသောသို့မဟုတ်ညီမျှသောဒြပ်စင်အရေအတွက်ကိုသိမ်းဆည်းရန် suffix frequency array ကိုဖန်တီးလိမ့်မည် ''i''  as ကြိမ်နှုန်း [i] ။

Lookup table ကြောင့်ယခုတွင်ရှိသော [1, N] အတွင်းရှိမည်သည့်ကိန်းဂဏန်းကိုမဆိုအဖြေတစ်ခုစစ်ဆေးနိုင်သည် အို (၁) အချိန်။ ဒါကငါတို့တစ် ဦး အမှုဖြစ်ပါတယ် အပေးအယူလုပ်သည် အချိန်မီတိုးတက်စေရန်မှတ်ဉာဏ်။ စားပွဲပေါ်မှာအရွယ်အစား N အရွယ်အစားရှိသဖြင့်မှတ်ဉာဏ်ကန့်သတ်ချက်များကိုလည်းကျွန်ုပ်တို့စိုးရိမ်စရာမရှိပါ။

 

ထက်ကြီးသောသို့မဟုတ်တူညီသော X Leetcode Solution ရှိသော X Element များပါ ၀ င်သည့်အထူး Array

algorithm

  1. ကန ဦး စတင်သည် အကြိမ်ရေ အဖြစ်တန်ဖိုးတစ်ခုစီရှိခြင်းအရွယ်အစား N ကိုခင်းကျင်း သုည
  2. ဒြပ်စင်တိုင်းသည် i  ခင်းကျင်းထဲမှာ:
    1. If i > N၊ ထပ်တိုးနှုန်း [N]
    2. တိုးမြှင့်သည့်ကြိမ်နှုန်း [i]
  3. မှ suffix sum array ကိုဖန်တီးပါ အကြိမ်ရေ အဖြစ်:
    1. ထံမှအထိတိုင်းဒြပ်စင်သည် i = N - 1 သို့ i = 0
      1. အစုံ ကြိမ်နှုန်း [i] = ကြိမ်နှုန်း [i] ကြိမ်နှုန်း [i + ၁]
  4. ကနေကွင်းဆက်ကို run i = 1 မှ i = N ကို
    1. If i == အကြိမ်ရေ [i] ပြန်လာပါ i
  5. -1 ပြန်လာ

အထူး Array အထူးပြု X ထက် ပို၍ ကြီးသောသို့မဟုတ်တူညီသော X Leetcode Solution ဖြင့်အသုံးပြုခြင်း

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';
}

Java အစီအစဉ်

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

အထူးပြု Array ကိုရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်းထက် ပို၍ ကြီးသောသို့မဟုတ် Equal X Leetcode Solution ဖြင့်အသုံးပြုခြင်း

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

အို (N), N ကို = ခင်းကျင်း၏အရွယ်အစား။ O (1) အချိန်တွင်မည်သည့် integer ကိုမဆိုကျွန်ုပ်တို့စစ်ဆေးနိုင်သည်၊ အဆိုးဆုံးအနေဖြင့် O (N) အချိန်ကိုအသုံးပြုသည်။

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

အို (N)။ ကြိမ်နှုန်းများကိုသိုလှောင်ရန် linear Memory Space ကိုသုံးသည်။