image

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

An operator The price define
with & If both bits are 1, the result is 1, otherwise the result is 0
or l If one of the two bits is 1, the result is 1, otherwise the result is 0
non ~ If the bits are 0, the result is 1, and if the bits are 1, the result is 0
Exclusive or ^ If the two bits are identical, the result is 0. If the two bits are different, the result is 1

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
The execution time

This article is formatted using MDNICE