Вопрос. В непустом массиве целых чисел nums каждый элемент появляется дважды, кроме одного. Найдите этот единственный.

Вы должны реализовать решение с линейной сложностью времени выполнения и использовать только постоянное дополнительное пространство.

Пример 1:

Input: nums = [2,2,1]
Output: 1

Пример 2:

Input: nums = [4,1,2,1,2]
Output: 4

Пример 3:

Input: nums = [1]
Output: 1

Линейная сложность времени выполнения

Важно понимать задачу, поэтому нам нужно понять, что такое линейная сложность выполнения.

Давайте сначала посмотрим на определение временной сложности.

В информатике временная сложность — это вычислительная сложность, которая описывает количество компьютерного времени, необходимого для запуска алгоритма. Временная сложность обычно оценивается путем подсчета количества элементарных операций, выполняемых алгоритмом, при условии, что выполнение каждой элементарной операции занимает фиксированное количество времени. Таким образом, время и количество элементарных операций, выполняемых алгоритмом, различаются не более чем на постоянный множитель. https://en.wikipedia.org/wiki/Time_complexity

В краткосрочной перспективе это время, необходимое для запуска функции. Таким образом, линейный, вероятно, будет означать линейный просмотр каждого элемента данных. Начнем с определения Википедии.

Говорят, что алгоритм требует линейного времени или O(n) времени, если его временная сложность составляет O. (н). Неформально это означает, что время работы увеличивается не более чем линейно с размером входных данных. Точнее, это означает, что существует константа c такая, что время выполнения не превышает cn для каждого входа размером n. Например, процедура суммирования всех элементов списка требует времени, пропорционального длине списка, если время добавления постоянно или, по крайней мере, ограничено константой. Линейное время — это наилучшая возможная временная сложность в ситуациях, когда алгоритм должен последовательно считывать весь ввод.

For loop будет, где проверяется каждый элемент массива, будет примером линейного запроса.

Решение

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

if (nums.length===1) {
    return nums[0]
}

Нам нужно будет создать переменную result.

let result = 0;

Я буду использовать цикл forEach, так как мы знаем, что нам нужно будет проверить каждый элемент массива.

nums.forEach(element => {
   result = result ^ element
});

Часть этого цикла, которая решает эту проблему, result = result ^ element, поэтому мы рассмотрим ее глубже. ^ означает XOR.

Побитовый оператор XOR (^) возвращает 1 в каждой битовой позиции, для которой соответствующие биты одного, но не обоих операндов равны 1.

XOR выполняет логическую операцию исключающее ИЛИ для каждого бита своих целочисленных аргументов и, глядя на приведенную выше таблицу истинности XOR: одно или другое верно, но не оба. Следовательно, если все значения в массиве, кроме одного, уникальны, в конечном итоге каждое повторяющееся значение будет аннулировать друг друга во время побитовых операций, и мы получим уникальное неповторяющееся значение.

Теперь мы можем просто вернуть result.

return result;

Код

Пожалуйста, проверьте меня в следующих социальных сетях, я буду рад услышать от вас! — LinkedIn, GitHub и Facebook.

Дополнительные материалы на plainenglish.io