Вопрос заключается в следующем:
Учитывая массив, содержащий n различных чисел, взятых из 0, 1, 2, ..., n, найдите то, которое отсутствует в массиве.
Например,
Учитывая числа = [0, 1, 3], возвращаем 2.
Примечание.
Ваш алгоритм должен работать с линейной сложностью во время выполнения. Не могли бы вы реализовать это, используя только постоянную сложность дополнительного пространства?
Таким образом, решить эту проблему было бы тривиально, если бы нам было позволено больше, чем постоянная сложность дополнительного пространства. Однако даже с этим ограничением эта проблема также довольно проста, если вы понимаете, что существует тесная связь между индексом i и значением массива [i]. На самом деле, они были бы одинаковыми, если бы не было дубликатов. Таким образом, у нас есть несколько подходов. Во-первых, мы могли выполнять побитовые операции. Поскольку a ^ b ^ b = a, мы можем использовать взаимосвязь между индексом массива и значением массива в наших интересах. Другой подход состоял бы в том, чтобы, поскольку мы знаем, что числа последовательны и находятся в пределах диапазона, вычислить ожидаемую сумму и просто вычесть каждый элемент массива из этой ожидаемой суммы.
Подход, который я использовал, является некоторой вариацией второго подхода. Вместо явного вычисления ожидаемой суммы я добавляю и вычитаю по ходу дела.
Обратите внимание, что ожидаемое значение начинается с nums.length, поскольку это значение индекса никогда не будет доступно i в цикле for.
