Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/260.html
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.
Algorithm
This question is actually a very clever use of the Single Number
solution, because that solution can accurately find a number that appears only once, but the premise is that other numbers must appear twice.
And this question has two numbers that only appear once, so if we can find a way to divide the original array into two small arrays, the two different numbers are in the two small arrays, so that the Single Number
solution is called separately You can get the answer.
So how to achieve it, first we XOR
all the original array, then we will get a number, this number is the result of the XOR of two different numbers, we take out any one of the bits that is ‘1’, For the sake of convenience, we use a &= -a
to take out the bit whose rightmost end is ‘1’, specifically how to operate this.
Take the example in the title, if we exclusive OR
all of them, we know that the exclusive OR
of the same two numbers is 0, then the two 1, and the two 2 are cancelled out, and there is nothing left 3 and 5’exclusive OR’, which is the binary 11 and 101’exclusive OR’, get 110.
Then we perform a &= -a
operation. First change the negative number. In binary, the negative number is in the form of complement, and the complement is the complement +1
, then the complement of 110
is 11...1001
, then after adding 1, it is 11...1010
, and then 110 And, get 10, which is the diff variable
in the code.
With this diff, the original array can be divided into two arrays. Why, if two identical numbers are XOR
, each of them will be 0, and different numbers will be XOR
, there must be different corresponding bits, one 0 and one 1, so XOR
‘ it’s 1.
For example, the binary 11
and 101
of 3
and 5
, if you look from low to high, the first difference is the second digit. Then we use the second digit to AND each number in the array. Depending on the result, it must be possible to distinguish 3 and 5, and because the other numbers appear in pairs, they are also paired. In the end, they will be XORed into 0, and 3 and 5 will not be affected. XOR the numbers in the two groups separately to get the final result.
Summarize:
- Initialize a variable eor (bitwise XOR) to 0.
- Iterate through each number x in nums and perform bitwise XOR with eor. This will result in eor storing the XOR of the two non-repeating numbers.
- Find the lowest set bit (lowbit) in eor using the expression lowbit = eor & (-eor). This will give a number with only the lowest set bit of eor set to 1, and all other bits set to 0.
- Initialize a list ans with two elements, both initially set to 0.
- Iterate through each number x in nums again:
- If (x & lowbit) == 0, it means the lowest set bit of x is different from the lowest set bit of eor. Therefore, x belongs to one group of non-repeating numbers. Perform bitwise XOR with ans[0] to find one non-repeating number.
- Otherwise, (x & lowbit) != 0, indicating that x belongs to the other group of non-repeating numbers. Perform bitwise XOR with ans[1] to find the other non-repeating number.
- Return the ans list containing the two non-repeating numbers.
Code
-
public class Single_Number_III { public static void main(String[] args) { int a = 7; int b = a & -a; System.out.println(Integer.toBinaryString(a)); // 111 // to negative, flip bits, and then +1 System.out.println(Integer.toBinaryString(-a)); //32 bits: 11111111111111111111111111111001 System.out.println(Integer.toBinaryString(b)); } public class Solution { public int[] singleNumber(int[] nums) { if (nums == null || nums.length == 0) { return new int[]{}; } // Pass 1 : // Get the XOR of the two numbers we need to find int diff = 0; for (int num : nums) { diff ^= num; } diff &= -diff; // Pass 2 : diff will distinguish two wanted numbers int[] rets = {0, 0}; // this array stores the two numbers we will return for (int num : nums) { if ((num & diff) == 0) { // the bit is not set rets[0] ^= num; } else { // the bit is set rets[1] ^= num; } } return rets; } } } ############ class Solution { public int[] singleNumber(int[] nums) { int eor = 0; for (int x : nums) { eor ^= x; } int lowbit = eor & (-eor); int[] ans = new int[2]; for (int x : nums) { if ((x & lowbit) == 0) { ans[0] ^= x; } } ans[1] = eor ^ ans[0]; return ans; } }
-
// OJ: https://leetcode.com/problems/single-number-iii/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> singleNumber(vector<int>& A) { int x = 0; for (int n : A) x ^= n; int lb = x & -(unsigned)x, a = 0; for (int n : A) { if (n & lb) a ^= n; } return {a, x ^ a}; } };
-
class Solution: def singleNumber(self, nums: List[int]) -> List[int]: eor = 0 for x in nums: eor ^= x lowbit = eor & (-eor) ans = [0, 0] for x in nums: if (x & lowbit) == 0: ans[0] ^= x else: ans[1] ^= x return ans ############ class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: List[int] """ xor = 0 for num in nums: xor ^= num xor = xor & -xor a, b = 0, 0 for num in nums: if num & xor: a ^= num else: b ^= num return a, b
-
func singleNumber(nums []int) []int { eor := 0 for _, x := range nums { eor ^= x } lowbit := eor & (-eor) ans := make([]int, 2) for _, x := range nums { if (x & lowbit) == 0 { ans[0] ^= x } } ans[1] = eor ^ ans[0] return ans }
-
/** * @param {number[]} nums * @return {number[]} */ var singleNumber = function (nums) { let eor = 0; for (const x of nums) { eor ^= x; } const lowbit = eor & -eor; let ans = [0]; for (const x of nums) { if ((x & lowbit) == 0) { ans[0] ^= x; } } ans.push(eor ^ ans[0]); return ans; };