LeetCode Notes: Single Number

#leetcode

Question

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

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

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.

Solution One

Analysis:

Using the principle that the key value of the js object cannot be repeated, counting the number of occurrences of each number, and then finding the number that only appears once, two cycles are required.

Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  const obj = {};

  //Count the number of occurrences of each number
  nums.forEach((item) => {
    if (!(item in obj)) {
      obj[item] = 1;
    } else {
      obj[item] += 1;
    }
  });

  //Get the number that appears once
  for (let i in obj) {
    if (obj[i] === 1) {
      return i;
    }
  }
  return 0;
};

Solution Two

Analysis:

Use the characteristic of Bitwise XOR to solve, one traverse.

  1. Satisfy the commutative law: a ^ b ^ c <=> a ^ c ^ b
  2. The exclusive Bitwise XOR of any number and 0 is any number: 0 ^ n => n
  3. The Bitwise XOR of the same number is 0: n ^ n => 0

So for example nums is [4,1,2,1,2]

4 ^ 1 ^ 2 ^ 1 ^ 2

Equivalent to

4 ^ 1 ^ 1 ^ 2 ^ 2

Equivalent to

4 ^ 0 ^ 0

Equivalent to

4

Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let result = nums[0];

  // Bitwise XOR
  nums.forEach((item, i) => {
    if (i !== 0) {
      result = result ^ item;
    }
  });

  return result;
};

For problems of the same type of solution, please refer to

LeetCode Notes: Find the Difference

Reference

Comments