3289.The Two Sneaky Numbers of Digitville

Ссылка на задачу: https://leetcode.com/problems/the-two-sneaky-numbers-of-digitville/description/

Описание

В городе Диджитвилль живет набор чисел nums, который содержит целые числа от 0 до n - 1. Каждое число должно присутствовать в массиве только один раз, однако два гадких числа оказались в нем дважды, делая массив длинее, чем он должен быть.

Как городской детектив, вы должны найти эти гадкие числа. Верните массив из этих двух чисел (в любом порядке), чтобы Диджитвилль снова мог спать спокойно.

Примеры

Пример 1

Input:

0	1	1	0

Output:

0	1

Объяснение: числа 0 и 1 появляются в массиве дважды.

Пример 2

Input:

0	3	2	1	3	2

Output:

2	3

Объяснение: числа 2 и 3 появляются в массиве дважды.

Ограничения

2 <= n <= 100
nums.length == n + 2
0 <= nums[i] < n
гарантируется, что в nums содержится именно 2 лишних числа

Решение

Способ 1

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

Алгоритм:

Инициализировать множество, чтобы запоминать количество повторений элементов
Перебрать все элементы nums и проверять, присутствует ли он в множестве
Если элемент уже есть в множестве, добавить элемент в искомый массив
Как только размер искомого массива станет равным 2, можно заранее прервать перебор элементов nums

Код:

python

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        was = set()

        ans = []

        for i in range(len(nums)):
            if nums[i] in was:
                ans.append(nums[i])

                if len(ans) == 2:
                    return ans
            was.add(nums[i])
        return ans

C++

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        unordered_set<int> was;

        vector<int> ans;

        for (int i = 0; i < nums.size(); ++i) {
            auto it = was.find(nums[i]);
            if (it != was.end()) {
                ans.push_back(nums[i]);
                if (ans.size() == 2) {
                    return ans;
                }
            }
            was.insert(nums[i]);
        }
        return ans;
    }
};

Сложность алгоритма по времени - O(N)

В данном случае мы перебираем все элементы массива nums размером n лишь один раз.

Сложность алгоритма по памяти - O(N)

Для реализации требуется дополнительный объект. В худшем случае его размер будет совпадать с размером исходного nums.

Способ 2

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

Алгоритм:

Отсортировать nums
Перебрать все элементы nums, проверяя на каждом шаге, равен ли текущий элемент предыдущему
Если элемент равен, то добавить его в искомый массив
Как только размер искомого массива станет равным 2, прервать перебор

Код:

python

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        nums.sort()

        ans = []

        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                ans.append(nums[i])

                if len(ans) == 2:
                    return ans

C++

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<int> ans;

        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] == nums[i - 1]) {
                ans.push_back(nums[i]);
                if (nums.size() == 2) {
                    return nums;
                }
            }
        }
        return ans;
    }
};

Сложность алгоритма по времени - O(N + NlogN)

Сначала необходимо отсортировать массив (это O(NlogN)), а затем - перебрать все его элементы (это O(N)).

Сложность алгоритма по памяти - O(1)

В данном решении не используется дополнительных объектов, под которые требовалось бы выделять память.

Способ 3

Можно не только не использовать дополнительную память, но и уменьшить сложность алгоритма до O(N), перебрав элементы лишь один раз.

Сказано, что каждое число в диапазоне от 0 до n - 1 должно встречаться в nums только раз, значит набор чисел представляет собой арифметическую прогрессию размером n. Сумма такой прогрессии - это n * (0 + max) / 2, где max = n - 1. Сумма прогрессии должна быть n * (n - 1) / 2.

Значение max мы можем определить без перебора всех элементов. В условии сказано, что размер последовательности должен быть n, а по факту он n + 2 (два лишних числа), то есть для нахождения n достаточно из длины массива вычесть 2.

Перебрав все элементы один раз, мы можем найти фактическую сумму nums. Мы знаем, что она больше правильной на x + y, где x и y - гадкие искомые числа.

Итак, первое уравнение у нас есть: n * (n - 1) / 2 + x + y = fact_sum.

Пока что у нас одно уравнение, две неизвестных. Нужно еще одно уравнение.

Теперь рассмотрим сумму квадратов арифметической прогрессии. Здесь тоже есть формула: n * (n + 1) * (2n + 1) / 6. Такое значение является правильным, а фактическое может быть найдено в процессе все того же перебора всех элементов nums. Фактическое значение больше правильного на величину x^2 + y^2.

Получаем второе уравнение: n * (n - 1) * (2n - 1) / 6 + x^2 + y^2 = fact_sum_sqr.

Обобщим: plan = n * (n - 1) / 2, plan_sqr = n * (n - 1) (2n - 1) / 6.

S = fact - plan

Q = fact_sqr - plan_sqr

Система уравнений:

x + y = S
x^2 + y^2 = Q

Выражая y через x, подставляя во второе уравнение и раскрывая скобки, получаем: 2x^2 - 2Sx + S^2 - Q = 0

Квадратное уравнение, вычисляем дискриминант и корни.

D = 4S^2 - 8(S^2 - Q)

x1 = (2S + sqrt(D)) / 4

x2 = (2S - sqrt(D)) / 4

Нас интересует тот x, который больше нуля (x1).

Алгоритм:

Вычислить n как len(nums) - 2
По формуле n * (n - 1) / 2 правильную рассчитать сумму арифметической прогрессии (plan)
По формуле n * (n - 1) * (2n - 1) / 6 рассчитать правильную сумму квадратов арифметической прогрессии (plan_sqr)
В рамках одного перебора всех элементов вычислить фактические сумму и сумму квадратов (fact и fact_sqr)
Вычислить значение S = fact - plan
Вычислить значение Q = fact_sqr - plan_sqr
Вычислить дискриминант D = 4S^2 - 8 * (S^2 - Q)
Вычислить первое гадкое число: x = (2S + sqrt(D)) / 4
Вычислить второе гадкое число y = S - x

Код:

python

class Solution:
    def getSneakyNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums) - 2

        plan = n * (n - 1) // 2

        plan_sqr = n * (n - 1) * (2*n - 1) // 6

        fact, fact_sqr = 0, 0

        for i in range(len(nums)):
            fact += nums[i]
            fact_sqr += nums[i] * nums[i]
        
        
        S = fact - plan

        Q = fact_sqr - plan_sqr

        D = 4 * S * S - 8 * (S * S - Q)

        x = (2 * S + int(sqrt(D))) // 4
        y = S - x

        return [x, y]

C++

class Solution {
public:
    vector<int> getSneakyNumbers(vector<int>& nums) {
        int n = nums.size() - 2;
        int plan = n * (n - 1) / 2;
        int plan_sqr = n * (n - 1) * (2*n - 1) / 6;

        int fact = 0;
        int fact_sqr = 0;
        for (int i = 0; i < nums.size(); ++i) {
            fact += nums[i];
            fact_sqr += nums[i] * nums[i];
        }

        int S = fact - plan;
        int Q = fact_sqr - plan_sqr;

        int D = 4 * S * S - 8 * (S * S - Q);

        int x = (2 * S + sqrt(D)) / 4;
        int y = S - x;

        return {x, y};
    }
};

Сложность алгоритма по времени - O(N)

В данном случае перебор элементов массива размером n всего один.

Сложность алгоритма по памяти - O(1)

Для решения используются дополнительные целочисленные переменные, размер которых не зависит от размера входного массива.