Привет всем! В этом блоге мы рассмотрим проблему leetcode номер 136.
Вопрос -
Учитывая непустой массив целых чисел 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
Анализ -
- Как мы видим, у нас есть непустой массив чисел, и все числа будут приходить дважды, ожидая одного числа, поэтому нам нужно выяснить, как проверить одно число, которое не повторяется, и мы вернем один элемент.
- В данном вопросе они упоминают "Вы должны реализовать решение с линейной сложностью времени выполнения и использовать только постоянное дополнительное пространство". что означает, что мы можем пройти один раз по этому массиву и не можем использовать дополнительное пространство. В любом случае, если мы используем дополнительное пространство, эту проблему будет легко решить, поскольку мы можем использовать hashmap.
- Итак, здесь мы можем попробовать с оператором XOR, так что все мы знаем об этом в дни учебы в колледже, когда мы изучали встроенный код или лаборатории, этот оператор XOR работает, как показано в таблице ниже.
- Если два элемента одинаковы, то есть 1–1 или 0–0, это вернет как «0», а если они разные, то есть 1 и 0, это вернет как «1».
- Давайте проверим пример один, это [2,2,1] вывод будет 1, потому что 2 ^ 2 -> 0, 2 ^ 1 -> 1.
Input: nums = [2,2,1] Output: 1
- Теперь давайте проверим, как мы можем работать с программой
class Solution { public int singleNumber(int[] nums) { int number=0; for(int i=0;i<nums.length;i++){ number = number^nums[i]; } return number; } }
- Итак, здесь мы взяли переменную «число» и присвоили ей значение «0», потому что любое число xor с 0 является самим числом.( 0 ^ n = n)
- И с помощью одного цикла for мы можем проверить число с помощью nums length и число с помощью xor с nums[i], так что любое число, которое является дубликатом, отменит себя и вернет «0». И последний отдельный элемент вернется как «число». Это даст вам успешный результат, и программа будет принята.
- Мы начали эту серию с основного вопроса, мы рассмотрим несколько вопросов и попытаемся решить их в следующих блогах.
Приятного чтения :)