Вы когда-нибудь сталкивались со сценарием, когда вам дан массив чисел, но одно из них отсутствует? Это как головоломка, ожидающая решения! В этой статье блога мы рассмотрим различные методы эффективного поиска недостающего числа в массиве с временной сложностью O(n). Итак, хватайте детективную шляпу и давайте окунемся в мир программирования!

Метод 1: подход на основе суммы разностей

Наш первый метод предполагает использование подхода разности сумм. Мы знаем, что сумма чисел от 1 до n дается по формуле (n*(n+1))/2. Вычислив реальную сумму массива и вычтя ее из ожидаемой суммы, мы можем найти недостающее число.

def find_missing_number(arr):
    n = len(arr) + 1
    expected_sum = (n * (n + 1)) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum

Метод 2: магия XOR

Еще один умный метод предполагает использование операции XOR (исключающее ИЛИ). Результатом операции XOR числа самого себя будет 0. Мы можем использовать это свойство, чтобы найти недостающее число, выполняя операцию XOR для всех элементов массива с числами от 1 до n. Недостающее число будет результатом XOR.

def find_missing_number(arr):
    n = len(arr) + 1
    xor_result = 0
    for i in range(1, n + 1):
        xor_result ^= i
    for num in arr:
        xor_result ^= num
    return xor_result

Метод 3: двоичный поиск

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

def find_missing_number(arr):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if (arr[mid] - mid) == (arr[0] - 0) + mid:
            low = mid + 1
        else:
            high = mid
    return arr[high] - 1

Метод 4. Хеширование

Используя хеш-таблицу или набор, мы можем эффективно найти недостающее число, перебирая массив и сохраняя каждый элемент. Затем мы выполняем итерацию от 1 до n и проверяем, существует ли каждое число в хеш-таблице или наборе. Недостающим номером будет тот номер, который не найден.

def find_missing_number(arr):
    n = len(arr) + 1
    num_set = set(arr)
    for i in range(1, n + 1):
        if i not in num_set:
            return i

В этой статье мы рассмотрели четыре различных метода поиска недостающего числа в массиве с временной сложностью O(n). Мы рассмотрели метод разности сумм, операцию XOR, двоичный поиск и хеширование. Каждый метод имеет свои преимущества и подходит для разных сценариев. Поняв эти методы, вы сможете эффективно решать головоломки с пропущенными числами в своих будущих начинаниях по программированию.

Итак, проверьте свои детективные навыки и взломайте код поиска недостающих чисел за время O(n)!