Трето решение за максимален брой Leetcode


Ниво на трудност Лесно
Често задавани в Амазонка Facebook Google
Array

Както се казва в заглавието, целта е да се намери третото максимално цяло число в дадено масив на цели числа. Имайте предвид, че трябва да намерим отчетлив трето максимално цяло число в масива. Връщаме максималното цяло число в масива, когато то няма ясно изразено трето максимално число.

Пример

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

Обяснение

Първият максимум е 3, вторият максимум е 2, а третият максимум е 1. И така, отпечатваме 1.

Array = {1 , 1 , 3}
3

Обяснение

Първият максимум е 3, вторият максимум е 1, но има Не. трети максимум, тъй като ние считаме и двете 1 за втори максимум тук.

Подход (сортиране)

Можем да сортираме целия масив и да намерим трети отличителен цяло число, започвайки от неговото обратно. Имайте предвид, че не можем да върнем Array [N - 3] просто тъй като в масива може да има дублирани записи. Ако не намерим 3 различни цели числа в масива, връщаме последния му елемент, тъй като е максималният елемент. Следвайте дадения алгоритъм за по-добро разбиране.

Трето решение за максимален брой Leetcode

алгоритъм

  1. Създайте функция thirdMax () връщане на необходимото цяло число
  2. thirdMax () връща третото различно максимално цяло число в даден масив- a
  3. Сортирайте масива
  4. Инициализирайте променлива, idx за съхраняване на последния индекс на масива и distinctCount за преброяване на отделните елементи отзад
  5. докато idx> = 0:
    • увеличение distinctCount
    • Инициализиране да итерира през индекси, имащи същата стойност като [idx]
    • докато елементите преди idx имат същата стойност като [idx] и i> = 0:
      • снижаване i
    • If i == -1, това означава, че сме обходили целия масив
      • Върнете [n - 1], максимален елемент, тъй като в масива няма дори 3 три отделни елемента
    • Присвояване idx = i за да преминете към следващия набор от максимални цели числа
    • If distinctCount е равно на 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 = размер на масива, докато сортираме целия масив.

Космическа сложност

O (1) тъй като използваме само постоянно пространство в паметта.

Подход (оптимален)

Оптималният подход тук е да се поддържат само три стойности, които ще съхраняват първото, второто и третото максимално число в масива. Има обаче някои основни случаи, като винаги трябва да разглеждаме отделни елементи като максимални. За тази цел, определен може да се използва, за да можем винаги да се отървем от дублиращи се елементи. Можем да прегледаме масива и да поддържаме размера на определен като 3 след всяка итерация. В случай че съдържа повече от 3 елемента след всяко вмъкване, ние изваждаме най-малкото от него, така че да съдържа трите отчетлив най-голям елементи в крайна сметка. Ако накрая размерът му е по-малък от 3, връщаме максималната му стойност.

алгоритъм

  1. Отново използваме същата функция thirdMax () за решаване на нашия проблем
  2. Инициализирайте набор, за да съхранявате максимални цели числа.
  3. За всеки елемент в масива:
    • Добавете го към комплекта
    • Ако размерът на комплекта надвишава 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 = размер на масива.

Космическа сложност

O (1) тъй като използваме само постоянно пространство в паметта.