Third Maximum Number

Условие

Дан массив целых чисел nums. Нужно вернуть третье по величине уникальное число в массиве. Если третьего максимального числа нет, верни наибольшее число.

Примеры

Input: nums = [3, 2, 1]

Output: 1

Explanation: Третье по величине уникальное число — 1.

Input: [1, 2]

Output: 2

Explanation: Третьего максимального числа нет, возвращаем максимальное число — 2.

Input: nums = [2, 2, 3, 1]

Output: 1

Explanation: Уникальные числа — [3, 2, 1]. Третье по величине — 1.

Решение

fun thirdMax(nums: IntArray): Int {
    val uniqueNums = nums.toSet()  // Убираем дубликаты, оставляя уникальные числа

    // Если уникальных чисел меньше 3, возвращаем максимум
    if (uniqueNums.size < 3) {
        return uniqueNums.maxOrNull()!!
    }

    // Иначе находим третье максимальное значение
    var first = Int.MIN_VALUE
    var second = Int.MIN_VALUE
    var third = Int.MIN_VALUE

    for (num in uniqueNums) {
        when {
            num > first -> {
                third = second
                second = first
                first = num
            }
            num > second -> {
                third = second
                second = num
            }
            num > third -> {
                third = num
            }
        }
    }

    return third
}

Временная сложность

O(n), где n — длина массива nums, так как мы проходим по массиву один раз для создания множества и один раз для поиска третьего максимального числа.

Пространственная сложность

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