Հատուկ զանգված ՝ ավելի քան X տարրերով Leetcode լուծույթով


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Google
Դասավորություն Հեշինգ

Խնդրի ՝ «Հատուկ զանգված X- ից ավելի կամ ավելի հավասար X տարրերով» խնդրի մեջ մեզ տրված է դասավորություն ոչ-բացասական ամբողջ թվերի: Մենք պետք է գտնենք X ամբողջ մի ամբողջ թիվ, որպեսզի զանգվածում լինի հենց իրենից մեծ կամ հավասար X տարրեր: Եթե ​​չկա հնարավոր X, որը բավարարում է այս պայմանը, մենք պետք է դուրս գանք -1:

Օրինակ

1 2 3 4
-1
1 3 4 5
3

Մոտեցում (կոպիտ ուժ)

Հաստատ է, որ եթե X լուծում կա, ապա X- ը միշտ եզակի կլինի:

Ապացուցված է.

Հաշվի առնենք, որ կան X և Y երկու լուծումներ, որոնք X! = Y. Եկեք ենթադրենք X <Y. Հիմա X- ից մեծ կամ հավասար տարրերի քանակը պետք է լինի X, քանի որ մենք դա համարում ենք լուծում: Բայց քանի որ Y> X, կան Y տարրեր X- ից մեծ կամ հավասար, այնպես, որ X! = Y. Ուստի X լուծում լինելու մեր ենթադրությունը սխալ է, քանի դեռ X և Y հավասար չեն:

Այսպիսով, միշտ կա եզակի լուծում, եթե լուծում գոյություն ունի: Այժմ կարելի է նաև եզրակացնել, որ եթե X լուծում է, ապա դրանից մեծ / հավասար տարրերի քանակը = X, որը պետք է պակաս լինի N- ից, որտեղ N = զանգվածի չափը (հնարավորինս առավելագույն տարրերի քանակով) = N):

Այսպիսով, եթե X լուծում գոյություն ունի, ապա այն պետք է ընկած լինի [1, N] միջակայքում:

[1, N] միջակայքում մենք կարող ենք ստուգել յուրաքանչյուր ամբողջ թիվ, թե արդյոք զանգվածի այն տարրերի քանակը, որոնք մեծ են կամ հավասար են միջակայքի ցանկացած ամբողջ թվերի, հավասար է հենց այդ ամբողջ թվին: Օրինակ ՝ դիտարկենք Array = {1, 3, 4, 5}: Այժմ 1-ը և 2-ը զանգվածում, համապատասխանաբար, ունեն դրանցից մեծ կամ հավասար 4 և 3 տարրեր: 3 – ից մեծ / հավասար տարրերի քանակը = 3: Այսպիսով, 3-ը միակ լուծումն է: Քանի որ մենք անցնում ենք ամբողջ ծառը ՝ գտնելու համար տարրերի քանակն ավելի մեծ, քան տիրույթում գտնվող յուրաքանչյուր ամբողջ թիվ: [1, N], այս մոտեցումը դանդաղ է:

Ալգորիթմ

  1. Գործարկել մի հանգույց i = 1-ից i = N լուծման ստուգման համար.
    • Հաշվի՛ր ավելի մեծ կամ հավասար տարրերի քանակը 'i'զանգվածում
      • Եթե ​​հաշվարկը հավասար է 'i', վերադարձիր i
  2. Վերադառնալ -1;

Իրականացում հատուկ զանգվածի X տարրերից ավելի մեծ կամ հավասար X Leetcode լուծման

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

Հատուկ զանգվածի բարդության վերլուծություն X Leetcode լուծումից ավելի քան կամ հավասար X տարրերով

Timeամանակի բարդություն

O (N * N), N = զանգվածի չափը: Ամենավատ դեպքում, երբ լուծումը X = N է, մենք O (N * N) համեմատություններ ենք անում:

Տիեզերական բարդություն

Ո (1), Օգտագործվում է միայն հիշողության անընդհատ տարածք:

Մոտեցում (օպտիմալ)

Մենք կարող ենք աղյուսակում պահել բոլոր տարրերի առաջացման քանակը ՝ օգտագործելով զանգված: Նշենք, որ N- ից մեծ արժեք ունեցող ցանկացած տարրի համար այն կարող ենք համարել որպես N արժեք ունեցող տարրի առաջացում, քանի որ լուծույթի առավելագույն արժեքը կարող է լինել N:

Այժմ X- ից մեծ կամ հավասար X- ի տարրերի հաճախականությունը X = հաճախականությունը X- ից մեծ է բոլոր տարրերի հաճախականությունը: [1, N] տիրույթում յուրաքանչյուր տարրի համար դա գտնելու համար մենք պետք է ունենանք ածանցային հաճախականության զանգված: ,

Այսպիսով, զանգվածի յուրաքանչյուր ամբողջ թվերի համար մենք պետք է սահմանենք հաճախություն [i] = հաճախություն [i] + հաճախություն [i + 1]յուրաքանչյուրի համարi'[N - 1, 1] տիրույթում, որը կստեղծի ածանցի հաճախականության զանգված `պահելով տարրերի քանակը ավելի մեծ կամ հավասար 'i'  as հաճախականություն [i]:

Այժմ, որոնման աղյուսակի պատճառով, մենք կարող ենք լուծում գտնել [1, N] միջակայքում գտնվող ցանկացած ամբողջ թիվի համար Ո (1) ժամանակը Սա այն դեպքն է, երբ մենք առեւտուր անել հիշողությունը ժամանակին բարելավելու համար: Քանի որ սեղանը N չափի է, մենք նաև հիշողության սահմանափակումներ չունենք:

 

Հատուկ զանգված ՝ ավելի քան X տարրերով Leetcode լուծույթով

Ալգորիթմ

  1. Նախաձեռնել ա հաճախություն 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 = N
    1. If i == հաճախականություն [i], վերադառնալ i
  5. վերադարձ -1

Իրականացում հատուկ զանգվածի X տարրերից ավելի մեծ կամ հավասար X Leetcode լուծման

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

Հատուկ զանգվածի բարդության վերլուծություն X Leetcode լուծումից ավելի քան կամ հավասար X տարրերով

Timeամանակի բարդություն

ՎՐԱ), N = զանգվածի չափը: Inteանկացած ամբողջ թիվ կարող ենք ստուգել O (1) ժամանակում, ուստի վատագույն դեպքում օգտագործում ենք O (N) ժամանակը:

Տիեզերական բարդություն

ՎՐԱ), Գծային հիշողության տարածությունն օգտագործվում է հաճախականությունները պահելու համար: