Ҳалли сеюми максималии рақами Leetcode


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Facebook Google
тартиботи ҳарбӣ

Тавре ки дар сарлавҳа гуфта мешавад, ҳадаф ёфтани сеюми максималии бутуни додашуда мебошад асал ададҳо. Дар хотир доред, ки ба мо лозим аст, ки фарқ мекунад адади сеюми максималӣ дар массив. Вақте ки он ягон бутуни максималии сеюми алоҳида надорад, мо шумораи бутуни ҳадди аксарро дар массив бармегардонем.

мисол

Array = {1 , 3 , 2 , -2 , -4 , -9}
1

Шарҳ

Максимум аввал 3, ҳадди дуюм 2 ва максимум сеюм 1. Ҳамин тавр, мо 1-ро чоп мекунем.

Array = {1 , 1 , 3}
3

Шарҳ

Ҳадди аввал 3, ҳадди дуввум 1, аммо вуҷуд дорад Не ҳадди сеюм, зеро мо ҳарду 1-ро ҳамчун ҳадди дуввуми инҷо баррасӣ мекунем.

Равиш (ҷобаҷогузорӣ)

Мо метавонем тамоми массивро ҷобаҷо кунем ва сеюми фарқ адади бутун аз он бозгашт. Аҳамият диҳед, ки мо массивро [N - 3] баргардонда наметавонем, зеро дар массив сабтҳои такрорӣ мавҷуданд. Агар мо намеёбем 3 ададҳои алоҳидаи массив, мо унсури охирини онро бармегардонем, зеро он унсури максималӣ аст. Барои фаҳмиши беҳтар алгоритми додашударо риоя кунед.

Ҳалли сеюми максималии рақами Leetcode

Алгоритм

  1. Функсия эҷод кунед thirdMax () баргардонидани бутуни зарурӣ
  2. thirdMax () сеюми бутуни алоҳидаи сеюмро дар массиви додашуда бар мегардонад - a
  3. Массивро ҷобаҷо кунед
  4. Тағирёбанда, idx барои нигоҳ доштани индекси охирини массив ва фарқият унсурҳои алоҳида аз қафо ҳисоб карда шаванд
  5. ҳол он idx> = 0:
    • Афзоиш фарқият
    • Оғоз такроран тавассути индекси дорои арзиши якхела [idx]
    • дар ҳоле ки унсурҳои пеш idx баробари [idx] ва доранд i> = 0:
      • Декор i
    • If i == -1, ин маънои онро дорад, ки мо тамоми массивро тай кардаем
      • A [n - 1] -ро баргардонед, ки унсури ҳадди аксарро дорад, зеро дар массив ҳатто 3 се унсури алоҳида набуданд
    • Таъиншуда idx = i барои гузаштан ба маҷмӯи навбатии максималии бутун
    • If фарқият ба 2 баробар аст,
      • ин маънои онро дорад, ки мо 2 унсури калонтар аз унсури ҳозираро тафтиш кардем (a [idx])
      • Бозгаштан унсури ҷорӣ, як [idx]
  6.  Барои синтаксиси функсия, баргардонед -1.
  7. Натиҷаро чоп кунед

Татбиқи ҳалли сеюми максималии рақами Leetcode

Барномаи C ++

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

int thirdMax(vector <int> &a)
{
    int n = a.size();
    sort(a.begin() , a.end());

    int idx = n - 1 , i , distinctCount = 0;

    while(idx >= 0)
    {
        distinctCount++;
        i = idx - 1;
        //to check all the values with same value as a[idx]
        while(i >= 0 && a[i] == a[idx])
            i--;

        //no third distinct element
        if(i == -1)
            return a[n - 1];
        idx = i;

        //found 2 bigger elements before?
        if(distinctCount == 2)
            return a[idx];
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

Барномаи Java

import java.util.Arrays;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        int n = a.length;
        Arrays.sort(a);

        int idx = n - 1 , i , distinctCount = 0;

        while(idx >= 0)
        {
            distinctCount++;
            i = idx - 1;
            //to check all the values with same value as a[idx]
            while(i >= 0 && a[i] == a[idx])
                i--;

            //no third distinct element
            if(i == -1)
                return a[n - 1];
            idx = i;

            //found 2 bigger elements before?
            if(distinctCount == 2)
                return a[idx];
        }
        return -1;
    }
}
1

Таҳлили мураккабии ҳалли сеюми максималии рақами Leetcode

Мураккабии вақт

O (NlogN), N = андозаи массив, вақте ки мо тамоми массивро ҷудо мекунем.

Мураккабии фазо

О (1) чунон ки мо танҳо фазои хотираи доимиро истифода мебарем.

Равиш (беҳтарин)

Усули оптималӣ ин нигоҳ доштани танҳо се арзишест, ки максимумҳои якум, дуюм ва сеюми максималиро дар массив нигоҳ медоранд. Аммо, баъзе ҳолатҳо асосӣ ҳастанд, ба монанди мо ҳамеша бояд унсурҳои гуногунро ҳадди аксар ҳисоб кунем. Бо ин мақсад, маҷмӯи истифода бурдан мумкин аст, то ки мо ҳамеша аз унсурҳои такрорӣ халос шавем. Мо метавонем тавассути массив такрор кунем ва андозаи маҷмӯи чун 3 пас аз ҳар такрор. Агар он пас аз дохилкунӣ зиёда аз 3 унсур дошта бошад, мо аз он элементҳои хурдтаринро мебарорем, то он се элементро дар бар гирад аз ҳама калонтарин унсурҳо дар охир. Агар андозаи он дар ниҳоят аз 3 камтар бошад, мо арзиши максималии онро бармегардонем.

Алгоритм

  1. Боз мо ҳамон функсияро истифода мебарем thirdMax () ки проблемам моро хал кунад
  2. Маҷмӯаро барои нигаҳдории максималии бутунҳо оғоз кунед.
  3. Барои ҳар як element дар массив:
    • Онро ба маҷмӯъ илова кунед
    • Агар андозаи маҷмӯа аз 3 зиёд бошад
      • Хориҷ / хориҷ кардани хурдтарин унсури маҷмӯа
  4. Агар андозаи маҷмӯа ба 3 баробар бошад
    • хурдтарин унсурро аз он баргардонед
  5. Эллис
    • унсури ҳадди аксарро дар он баргардонед
  6. Натиҷаро чоп кунед

Татбиқи ҳалли сеюми максималии рақами Leetcode

Барномаи C ++

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

int thirdMax(vector <int> &a)
{
    set <int> maxElements;
    for(int &element : a)
    {
        maxElements.insert(element);
        if(maxElements.size() > 3)
            maxElements.erase(*maxElements.begin());
    }
    if(maxElements.size() == 3)
        return *maxElements.begin();

    return *prev(maxElements.end());
}

int main()
{
    vector <int> a = {1 , 3 , 2 , -2 , -4 , -9};
    cout << thirdMax(a) << '\n';
}

Барномаи Java

import java.util.*;

class third_max
{
    public static void main(String args[])
    {
        int[] a = {1 , 3 , 2 , -2 , -4 , -9};
        System.out.println(thirdMax(a));
    }

    static int thirdMax(int[] a)
    {
        Set <Integer> maxElements = new HashSet <>();
        for(int element : a)
        {
            maxElements.add(element);
            if(maxElements.size() > 3)
                maxElements.remove(Collections.min(maxElements));
        }

        if(maxElements.size() == 3)
            return Collections.min(maxElements);
        return Collections.max(maxElements);
    }
}
1

Таҳлили мураккабии ҳалли сеюми максималии рақами Leetcode

Мураккабии вақт

О (Н) чунон ки мо аз массив дар як гузариш такрор мекунем. Ҳазф ва дохил кардани унсурҳо дар маҷмӯъ вақти доимиро талаб мекунад, зеро мо пас аз ҳар такрор дар он ҳадди аксар 3 элементро нигоҳ медорем. Ин ҷо, N = андозаи массив.

Мураккабии фазо

О (1) чунон ки мо танҳо фазои хотираи доимиро истифода мебарем.