Алгоритмы и структуры данных

Найти повторяющееся число

Проблема: Дан массив целых чисел nums, содержащий n + 1 целое число. Каждое целое число в nums находится в диапазоне [1, n] включительно.

Каждое целое число встречается ровно один раз, за ​​исключением одного целого числа, которое встречается два или более раз. Необходимо реализовать алгоритм, который возвращает число, которое встречается более одного раза.

Решение не изменяет числа массива и использует O(1) дополнительное пространство.

Один из наиболее эффективных методов использует идею цикла (tortoise and hare), аналогичную той, которая используется в проблеме обнаружения цикла в связном списке.

Пример 1: Input: nums = [1,2,3,2,2]
Output: 2

Пример 2: Input: nums = [1,2,3,4,4]
Output: 4

www.tgoop.com/the_algorithms/4897

4.8K viewsDec 9, 2024 at 18:02

Найти повторяющееся число

Проблема: Дан массив целых чисел nums, содержащий n + 1 целое число. Каждое целое число в nums находится в диапазоне [1, n] включительно.

Каждое целое число встречается ровно один раз, за ​​исключением одного целого числа, которое встречается два или более раз. Необходимо реализовать алгоритм, который возвращает число, которое встречается более одного раза.

Решение не изменяет числа массива и использует O(1) дополнительное пространство.

Один из наиболее эффективных методов использует идею цикла (tortoise and hare), аналогичную той, которая используется в проблеме обнаружения цикла в связном списке.

Пример 1: Input: nums = [1,2,3,2,2]
Output: 2

Пример 2: Input: nums = [1,2,3,4,4]
Output: 4

BY Алгоритмы и структуры данных