Блог

 class Solution {
public:
    int thirdMax(vector<int>amp; nums) 
    {
        int first = INT_MIN;
        int second = INT_MIN;
        int third = INT_MIN;
        
        for(int i=0; i<nums.size(); i  )
        {
            if(nums[i] > first)
            {
                third = second;
                second = first;
                first = nums[i];
            }
            else if(nums[i] > second amp;amp; nums[i] != first)
            {
                third = second;
                second = nums[i];
            }
            else if(nums[i] > third amp;amp; nums[i] != first amp;amp; nums[i] != second)
            {
                third = nums[i];
            }
        }
        
        if(third == INT_MIN)
            return first;
        else
            return third;
    }
};
  

Этот код предназначен для поиска третьего по величине числа, и если оно не существует, то возвращает первое по величине число. Большинство тестовых примеров выполнены успешно, но как мне использовать этот метод для
[1,2,-2147483648], где один из элементов массива сам по себе является INT_MIN ?

Вы могли бы избежать «наполнения» INT_MIN особым значением и вместо этого использовать std::optional . Этот класс предназначен для того, чтобы отличать случай «нет значения» или «пусто» от фактического значения.

С помощью опций вы можете выразить то, что вы на самом деле хотите явно проверить, т. Е. Не То, больше или меньше число INT_MIN , а скорее, есть ли у вас уже «первое по величине», «второе по величине» и т. Д.

 int third_highest(const::vector<int>amp; nums) 
{
    std::optional<int> highest[3];

    if (nums.empty()) { 
        throw std::invalid_argument("Expected a non-empty sequence of integers");
    }
    
    for(auto x : nums) {
        if (not highest[0].has_value()) { highest[0] = x; continue; }
        if (x > highest[0].value()) {
            highest[2] = highest[1];
            highest[1] = highest[0];
            highest[0] = x;
            continue;
        }
        if (not highest[1].has_value()) { highest[1] = x; continue; }
        if (x > highest[1].value()) {
            highest[2] = highest[1];
            highest[1] = x;
            continue;
        }
        if (not highest[2].has_value()) { highest[2] = x; continue; }
        if (x > highest[2].value()) {
            highest[2] = x;
            continue;
        }
    }
    return highest[2] ? highest[2].value() : highest[0].value(); 
}
  

… и на самом деле, это можно упростить и сократить еще больше, если вы перебираете highest значения; или если вы создаете highest небольшой вектор, размер которого постепенно увеличивается от 0 до 3.

_{PS — Вы не должны использовать «класс решения». Это плохая идея оборачивать функции в классы без причины.}

Я бы проверил, равен ли размер вектора < 3, вместо того, чтобы проверять, является ли третье значение INT_MIN

 if(nums.size() < 3)
            return first;
        else
            return third;
  

Редактировать:
Итак, я понимаю, что ваш код не учитывает повторяющиеся значения. Моим решением для этого было бы добавление счетчика для отслеживания количества уникальных элементов, а затем проверка наличия как минимум 3 уникальных значений или нет

 class Solution {
public:
    int thirdMax(vector<int>amp; nums) 
    {
        int first = INT_MIN;
        int second = INT_MIN;
        int third = INT_MIN;
        int counter = 0;
        
        for(int i=0; i<nums.size(); i  )
        {
            if(nums[i] > first)
            {
                third = second;
                second = first;
                first = nums[i];
                counter  ;
            }
            else if(nums[i] > second amp;amp; nums[i] != first)
            {
                third = second;
                second = nums[i];
                counter  ;
            }
            else if(nums[i] > third amp;amp; nums[i] != first amp;amp; nums[i] != second)
            {
                third = nums[i];
                counter  ;
            }
        }
        
        if(counter < 3)
            return first;
        else
            return third;
    }
};
  

Вам не нужно значение меньше INT_MIN . Не существует int меньшего, чем INT_MIN .

Ваша реальная проблема может быть решена путем сортировки вектора в порядке убывания (при условии, что у вас все в порядке с O(n log n) решением):

 #include <algorithm>
#include <vector>

int thirdMax(std::vector<int>amp; nums) {
    // trivial cases
    if (nums.size() == 0) return -42; // or throw an exception ?
    if (nums.size() == 1) return nums[0];
    // sort
    std::sort(nums.begin(),nums.end(),std::greater<int>());
    // third largest
    if (nums.size() > 2) return nums[2];
    // otherwise largest
    return nums[0];
}
  

Я хочу предложить другое решение, чтобы использовать только отдельные значения, как задается вопрос

(ab)Используйте a std::set !

 #include<vector>
#include<set>
#include<functional>
#include<iterator>

class Solution {
public:
    int thirdMax(std::vector<int> constamp; nums) {
        if (nums.size() == 0) return -42; // I like this one.
        std::set<int, std::greater<int>> s(cbegin(nums), cend(nums));
        if (s.size() > 2) return *next(cbegin(s),2);
        return *cbegin(s);
    }
};
  

Моя идея заключается в использовании флагов существования.

 class Solution {
public:
    int thirdMax(vector<int>amp; nums) 
    {
        int first = INT_MIN;
        int second = INT_MIN;
        int third = INT_MIN;
        bool firstExists = false, secondExists = false, thirdExists = false;
        
        for(int i=0; i<nums.size(); i  )
        {
            if(!firstExists || nums[i] > first)
            {
                third = second;
                second = first;
                first = nums[i];
                firstExists = true;
            }
            else if((!secondExists || nums[i] > second) amp;amp; nums[i] != first)
            {
                third = second;
                second = nums[i];
                secondExists = true;
            }
            else if((!thirdExists || nums[i] > third) amp;amp; nums[i] != first amp;amp; nums[i] != second)
            {
                third = nums[i];
                thirdExists = true;
            }
        }
        
        if(!thirdExists)
            return first;
        else
            return third;
    }
};
  

Поскольку вам нужен весь int домен, использование магического числа like INT_MIN не будет работать правильно.

Использование std::optional<int> в качестве типа для first , second , и third является решением здесь.

Соответствующим образом настройте условные обозначения: if (first) вычисляется true тогда и только тогда, когда first имеет явно установленное значение, и используется *first для доступа к значению, если оно имеет явно установленное значение.