Question

260. Single Number III

中文文档

Description

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

 

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

 

Constraints:

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Each integer in nums will appear twice, only two integers will appear once.

Solutions

Solution 1: Bitwise Operation

The XOR operation has the following properties:

• Any number XOR 0 is still the original number, i.e., $x \oplus 0 = x$;
• Any number XOR itself is 0, i.e., $x \oplus x = 0$;

Since all numbers in the array appear twice except for two numbers, we can perform XOR operation on all numbers in the array to get the XOR result of the two numbers that only appear once.

Since these two numbers are not equal, there is at least one bit that is 1 in the XOR result. We can use the lowbit operation to find the lowest bit of 1 in the XOR result, and divide all numbers in the array into two groups based on whether this bit is 1 or not. This way, the two numbers that only appear once are separated into different groups.

Perform XOR operation on each group separately to obtain the two numbers $a$ and $b$ that only appear once.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

class Solution:
  def singleNumber(self, nums: List[int]) -> List[int]:
    xs = reduce(xor, nums)
    a = 0
    lb = xs & -xs
    for x in nums:
      if x & lb:
        a ^= x
    b = xs ^ a
    return [a, b]

class Solution {
  public int[] singleNumber(int[] nums) {
    int xs = 0;
    for (int x : nums) {
      xs ^= x;
    }
    int lb = xs & -xs;
    int a = 0;
    for (int x : nums) {
      if ((x & lb) != 0) {
        a ^= x;
      }
    }
    int b = xs ^ a;
    return new int[] {a, b};
  }
}

class Solution {
public:
  vector<int> singleNumber(vector<int>& nums) {
    long long xs = 0;
    for (int& x : nums) {
      xs ^= x;
    }
    int lb = xs & -xs;
    int a = 0;
    for (int& x : nums) {
      if (x & lb) {
        a ^= x;
      }
    }
    int b = xs ^ a;
    return {a, b};
  }
};

func singleNumber(nums []int) []int {
  xs := 0
  for _, x := range nums {
    xs ^= x
  }
  lb := xs & -xs
  a := 0
  for _, x := range nums {
    if x&lb != 0 {
      a ^= x
    }
  }
  b := xs ^ a
  return []int{a, b}
}

function singleNumber(nums: number[]): number[] {
  const xs = nums.reduce((a, b) => a ^ b);
  const lb = xs & -xs;
  let a = 0;
  for (const x of nums) {
    if (x & lb) {
      a ^= x;
    }
  }
  const b = xs ^ a;
  return [a, b];
}

impl Solution {
  pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
    let xs = nums.iter().fold(0, |r, v| r ^ v);
    let lb = xs & -xs;
    let mut a = 0;
    for x in &nums {
      if (x & lb) != 0 {
        a ^= x;
      }
    }
    let b = xs ^ a;
    vec![a, b]
  }
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var singleNumber = function (nums) {
  const xs = nums.reduce((a, b) => a ^ b);
  const lb = xs & -xs;
  let a = 0;
  for (const x of nums) {
    if (x & lb) {
      a ^= x;
    }
  }
  const b = xs ^ a;
  return [a, b];
};

public class Solution {
  public int[] SingleNumber(int[] nums) {
    int xs = nums.Aggregate(0, (a, b) => a ^ b);
    int lb = xs & -xs;
    int a = 0;
    foreach(int x in nums) {
      if ((x & lb) != 0) {
        a ^= x;
      }
    }
    int b = xs ^ a;
    return new int[] {a, b};
  }
}