136. A number that appears only once

Topic describes

Given an array of non-empty integers, each element appears twice except for one element. Find me the element that only appears once. And it’s best if you don’t use extra space.

The sample

[1.2.1]; // 2 occurs only once in the array, so 2 is the solution
[1.2.1.2.3]; // 3 only appears once in the array, so 3 is the solution
Copy the code

Their thinking

  • The general idea is that we go through a set of numbers, keep track of how many times each number appears, and then find the one that only appears once
  • But this kind of problem, of course, requires extra space to record.
  • So we can only do it on the original array, but how can we do it on the original array without affecting the value that we want?
  • Again, every other element appears twice, but none of these numbers are what we want.
  • What if we could make them cancel each other out, like elimination music. Well, the rest is all we need
  • Then he came and he was xor

Exclusive or

  • The xor of the same number is 0

    • n ^ n = 0;
Copy the code

  • 0 xor any number is any number

    • 0 ^ n = n;
Copy the code

  • Satisfy commutative law

    • a ^ b ^ c = c ^ b ^ a
Copy the code

Taking the array [1, 2, 1, 2, 3] above as an example, we can convert it to

1 ^ 2 ^ 1 ^ 2 ^ 3;

// We can do the transformation because it satisfies the commutative law
1 ^ 1 ^ 2 ^ 2 ^ 3;

// Because the same number is xor 0, so finally become
0 ^ 3;

// 0 xor any is any number
3 // That's it
Copy the code

code

var singleNumber = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    nums[0] = nums[0] ^ nums[i];
  }
  return nums[0];
};
Copy the code