X элементтерінен үлкен немесе тең X Leetcode ерітіндісінен тұратын арнайы массив


Күрделілік дәрежесі оңай
Жиі кіреді Google
Array Хэш

«X элементтерінен үлкен немесе тең X-ге тең арнайы массив» деген есепте бізге ан берілген массив теріс емес бүтін сандар. Массивте оған тең немесе оған тең дәл X элементтері болатындай етіп біз бүтін Х санын табуымыз керек. Егер бұл шартты қанағаттандыратын X мүмкін болмаса, біз -1 шығаруымыз керек.

мысал

1 2 3 4
-1
1 3 4 5
3

Тәсіл (қатал күш)

Егер X шешімі болса, онда екені сөзсіз Х әрдайым ерекше болады.

Дәлелдеу:

X және Y екі шешімі бар, олар X! = Y. Х <Y деп қабылдайық. Енді Х-тен үлкен немесе оған тең элементтер саны X болуы керек, өйткені біз оны шешім деп санаймыз. Бірақ, Y> X болғандықтан, X-тен үлкен немесе оған тең Y элементтері бар, олар X! = Y. Демек, X пен Y тең болмайынша, 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 леткод ерітіндісінен үлкен элементтермен арнайы массивтің күрделілігін талдау

Уақыттың күрделілігі

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 өлшемді болғандықтан, бізде жады шектеулеріне алаңдамайды.

 

X элементтерінен үлкен немесе тең 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 леткод ерітіндісінен үлкен элементтермен арнайы массивтің күрделілігін талдау

Уақыттың күрделілігі

O (N), N = жиымның өлшемі. Біз кез-келген бүтін санды O (1) уақытта тексере аламыз, сондықтан нашар жағдайда O (N) уақытты қолданамыз.

Ғарыштың күрделілігі

O (N). Сызықтық жад кеңістігі жиіліктерді сақтау үшін қолданылады.