Number II, bit operators: NOT, AND, AND XOR that occur only once

Given an array of non-empty integers, every element appears three times except one. Find the element that appears only once.

Description:

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

The sample1: Input: [2.2.3.2] output:3
Copy the code

The sample2: input:0.1.0.1.0.1.99] output:99
Copy the code

Their thinking

• 1. Iterate through the input array, counting the number of occurrences of each number, and finally returning the number of occurrences of 1.
• 2. Bit operators: NOT, AND, AND XOR

Solution 1: count times + filter

The solution is more conventional

• 1. Count the number of occurrences of each element
• 2. Find an element that appears only once;

/** * @param {number[]} nums * @return {number} */
var singleNumber = function(nums) {
 var obj = {};
 //1. Count the occurrences of each element
 for (var i = 0; i < nums.length; i++) {
  var key = nums[i];
  if (obj[key]) {
   obj[key]++;
  } else {
   obj[key] = 1; }}//2. Find elements that occur only once
 for (var k in obj) {
  if (obj[k] === 1) {
   return k
  }
 }
};
Copy the code

Solution Method two-bit operator solution

For example,

With &

And algorithm: the result is “1” only if both digits are “1”; otherwise, it is 0

5 & 1 = 1
Copy the code

Or |

Or algorithm: one of the two digits is “1”, the result is “1”, otherwise it is 0

5| 1 = 5
Copy the code

non

Non-operators: Unary operators

• 0000 0000 0000 0000 0101
• If the operation is reversed: 1111 1111 1111 1111 1111 1111 1111 1111 1010 All signed integers are represented by complement. Complement = inverse +1
• 1. 1000 0000 0000 0000 0000 0000 0000 0101
• 1000 0000 0000 0000 0000 0000 0000 0000 0110

 ~5 = - 6
Copy the code

Exclusive or ^

Xor: if the two digits are different, the result is “1”, otherwise it is 0. 5^1 = 4

The left < <

Left shift: Move a number of bits to the left, supplementing 5<< 1 = 10 with 0

Moves to the right > >

Right shift algorithm: Move a number of digits to the right 5>>1 = 2

The problem solving code

/** * @param {number[]} nums * @return {number} */
var singleNumber = function(nums) {
 var ones = 0,
  twos = 0;
 for (var i = 0; i < nums.length; i++) {
  ones = ones ^ nums[i] & ~twos;
  twos = twos ^ nums[i] & ~ones;
 }
 return ones
};
Copy the code

This article is formatted using MDNICE