Topic describes

All but two digits appear twice in an integer array nums. Write a program to find these two numbers that only appear once. The time complexity is O(n), and the space complexity is O(1).

Example 1:

Input: nums = [4,1,4,6] output: [1,6] or [6,1]Copy the code

Example 2:

Input: nums = [1,2,10,4,1,4,3] output: [2,10] or [10,2]Copy the code

Limitations:

  • 2 <= nums <= 10000

solution

The XOR operation is solved.

First of all, it’s clear that the result after xor of two identical numbers is 0. Applying xOR to all the elements of the array results in the xor of two numbers that occur only once, namely eOR = a ^ b

Find out the number in the result EOR whose last bit is 1 and the rest of the bits are 0, that is, eOR & (~ eOR + 1), and then iterate through all the elements of the group, xor to a of the elements with 0 bits.

If b = eOR ^ a, return the result.

Python3

class Solution: def singleNumbers(self, nums: List[int]) -> List[int]: eor = 0 for num in nums: A = 0 for num in nums: if (num & diff) == 0: a ^= num b = eor ^ a return [a, b]Copy the code

Java

class Solution { public int[] singleNumbers(int[] nums) { int eor = 0; for (int num : nums) { eor ^= num; Int diff = eor & (~eor + 1); int a = 0; for (int num : nums) { if ((num & diff) == 0) { a ^= num; } } int b = eor ^ a; return new int[]{a, b}; }}Copy the code

JavaScript

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumbers = function (nums) {
  let eor = 0;
  for (let num of nums) {
    eor ^= num;
  }
  const diff = eor & (~eor + 1);
  let a = 0;
  for (let num of nums) {
    if ((num & diff) == 0) {
      a ^= num;
    }
  }
  let b = eor ^ a;
  return [a, b];
};
Copy the code