Поиск дубликата в массиве

Решение

Подход

Это одна из классических задач на собеседованиях Google, Amazon и других FAANG компаний. Ключевая идея — использовать сам массив как хеш-таблицу, помечая посещённые индексы через изменение знака значений.

Основное решение (O(1) память)

func findDuplicate(_ nums: inout [Int]) -> Int? {
    for num in nums {
        let index = abs(num) - 1  // Число от 1 до N, индекс от 0 до N-1
        
        // Если значение уже отрицательное, это индекс повторяющегося числа
        if nums[index] < 0 {
            return abs(num)
        }
        
        // Помечаем посещение, меняя знак
        nums[index] = -nums[index]
    }
    
    return nil
}

Немутирующее решение (если нельзя менять массив)

Если изменение исходного массива недопустимо, используем Floyd's Cycle Detection (алгоритм "черепаха и заяц"):

func findDuplicateWithoutMutation(_ nums: [Int]) -> Int? {
    // Фаза 1: Обнаружение цикла
    var slow = nums[0]
    var fast = nums[0]
    
    // Двигаем slow на 1 шаг, fast на 2 шага
    repeat {
        slow = nums[slow]
        fast = nums[nums[fast]]
    } while slow != fast
    
    // Фаза 2: Поиск начала цикла
    slow = nums[0]
    while slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }
    
    return slow
}

Альтернативное решение (O(n) память, если допустимо)

Это решение проще, но использует дополнительную память:

func findDuplicateWithSet(_ nums: [Int]) -> Int? {
    var seen = Set<Int>()
    
    for num in nums {
        if seen.contains(num) {
            return num
        }
        seen.insert(num)
    }
    
    return nil
}

Тестирование

// Тест 1: Дубликат в середине
var test1 = [3, 1, 3, 4, 2]
if let duplicate = findDuplicate(&test1) {
    print("Дубликат: \(duplicate)")  // Output: 3
}
print("Массив после: \(test1)")

// Тест 2: Дубликат в начале
var test2 = [2, 5, 9, 4, 2, 6, 7, 3, 8, 1]
if let duplicate = findDuplicate(&test2) {
    print("Дубликат: \(duplicate)")  // Output: 2
}

// Тест 3: Несколько дубликатов (найдёт первый)
var test3 = [1, 1]
if let duplicate = findDuplicate(&test3) {
    print("Дубликат: \(duplicate)")  // Output: 1
}

// Без мутации
let test4 = [1, 3, 4, 2, 2]
if let duplicate = findDuplicateWithoutMutation(test4) {
    print("Дубликат (без мутации): \(duplicate)")  // Output: 2
}

Как работает решение с изменением знака

Пример: [3, 1, 3, 4, 2]

1. Итерация 1: num = 3 → index = 2 → nums[2] = -3 → массив: [3, 1, -3, 4, 2]
2. Итерация 2: num = 1 → index = 0 → nums[0] = -3 → массив: [-3, 1, -3, 4, 2]
3. Итерация 3: num = -3 → index = 2 → nums[2] уже -3 → дубликат найден! Возвращаем 3

Как работает Floyd's Cycle Detection

Массив можно представить как linked list, где nums[i] указывает на следующий индекс:

• Дубликат создаёт цикл в этой виртуальной связной ссылке
• Алгоритм находит точку входа в цикл, что соответствует дубликату

Сложность:

• Время: O(n) — проходим массив один раз
• Память: O(1) — не используем дополнительные структуры

Сравнение подходов

Рекомендация для интервью

1. Сначала объясните Set решение — покажите понимание проблемы
2. Затем предложите оптимизацию — алгоритм с изменением знака или Floyd's Cycle
3. Выберите Floyd's Cycle, если нельзя менять исходные данные — это показывает глубокое понимание

Эта задача различает junior и senior разработчиков. Junior объясняет Set подход, senior сразу видит O(1) решение.