This is the 9th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The title

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

Description:

Your algorithm should have linear time complexity. Can you do it without using extra space?

Example 1:

Input: [2,2,1] output: 1Copy the code

Example 2:

Input: [4,1,2, 2] Output: 4Copy the code

thinking

Without considering the limitations of time complexity and space complexity, there are several solutions:

  • Use a hash table to store each number and the number of occurrences of that number.
  • Use collections to store numbers. The first iteration adds the element to the collection, and the second iteration removes the element from the collection.
  • Use the set to redo, sum, and then with the result of the sum before redo to do mathematical operations.

All of the above methods require space complexity of O(n), where n is the length of the array.

How do you optimize the solution to achieve linear time complexity and constant space complexity?

The answer is to use bit operations, with xor operations to optimize the solution.

Xor operations have the following three properties:

  • Any number xor with 0 will still be the same number.
  • Any number xor with itself, the result is 0.
  • Xor operations satisfy commutative and associative laws.

So, for the array NUMs, xOR is applied to each element in turn, and since xor is applied to a number that occurs twice, the end result is a number that occurs only once, which is the solution of method two.

The bitwise solution looks a lot more elegant!

answer

Method 1: hash table

var singleNumber = function(nums) {
  let map = new Map(a)let ans = 0;
  for(const num of nums){
    map.set(num, (map.get(num) || 0) + 1)}for(const [num, val] of map.entries()) {
    if(val === 1) {
      ans = num
    }
  }
  return ans;
};
Copy the code

Complexity analysis

  • Time complexity: O(n), where n is the length of array NUMs.
  • Space complexity: O(n), that is, the space required by hash mapping.

Method two: bit operation

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

Complexity analysis

  • Time complexity: O(n), where n is the length of array NUMs. You only need to iterate through the array once.
  • Space complexity: O(1).