Привет всем! В этом блоге мы рассмотрим проблему 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». И последний отдельный элемент вернется как «число». Это даст вам успешный результат, и программа будет принята.
  • Мы начали эту серию с основного вопроса, мы рассмотрим несколько вопросов и попытаемся решить их в следующих блогах.

Приятного чтения :)