This is the 21st day of my participation in the August Text Challenge.More challenges in August

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

【LeetCode 137. Numbers that occur only once II】 – JavaScript(Hash table + Math Trick + bitwise)

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

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

Solution 1: The most intuitive hash table

The solution is very simple, directly through an array, and then count the number of occurrences of each number, into a hash table.

The hash table is then iterated over again, returning the number of occurrences of 1.

The code implementation is as follows:

var singleNumber = function(nums) {
  const map = new Map(a);for (let num of nums) {
    if (map.has(num)) map.set(num, map.get(num) + 1);
    else map.set(num, 1);
  }

  for (let [num, times] of map.entries()) {
    if (times === 1) returnnum; }};Copy the code

However, this solution uses the extra O(N) space to open up the hash table.

Solution 2: Math

Suppose that for a, B, C, and D, D occurs once and other numbers occur three times. 2 * d = 3*(a + b + c + d) – (3a + 3b + 3c + d)

To compute (a + b + c + d), we can subtract the array and sum it. The de-duplication is aided by sets.

The code implementation is as follows:

var singleNumber = function(nums) {
  const set = new Set(nums);
  let sum1 = 0;
  for (let num of set.values()) {
    sum1 += num;
  }
  let sum2 = 0;
  for (let num of nums) {
    sum2 += num;
  }

  return Math.floor((3 * sum1 - sum2) / 2);
};
Copy the code

Again, this method uses order N extra space.

Solution 3: bit operation

The best solution to the problem is bitwise operations. Can accomplish requirements without creating extra space.

In terms of bits (up to 32 bits), the key to this approach is to figure out which bits are 1 for a number that occurs only once.

The overall algorithm flow is as follows:

  • Let’s start at number one
  • Create a mask (current bit is 1, other bits are 0) and set count to 0
  • Will carry each number and mask&Operation, if the result is not 0, count plus 1
  • If count is divisible by 3, it means that the digit that appears once is not 1; Otherwise, it means that the digit that appears once is 1
  • Continue to check the second digit, all the way to the 32nd digit, end
var singleNumber = function(nums) {
  let res = 0;
  for (let bit = 0; bit < 32; ++bit) {
    let mask = 1 << bit;
    let count = 0;
    for (let num of nums) {
      if (num & mask) ++count;
    }
    if (count % 3) { res = res | mask; }}return res;
};
Copy the code

Time is O(N), space is O(1).

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤