This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

260. The number III that occurs only once

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

Advanced: Your algorithm should have linear time complexity. Can you do this using just constant space complexity?

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]Copy the code

Tip:

  • 2 <= nums.length <= 3 * 10^4
  • 2 ^31 <= nums[i] <= 2^31 – 1
  • All numbers in NUMS occur twice except for two integers that occur only once

Their thinking

  • Because exactly two elements appear only once, and all the others appear twice, xor all the elements, the same elements cancel each other out, so the result of xor is xor of two different elements
  • And since the elements of two different binary representation there will be a different, but not the same binary 1 is the exclusive or results of the digital, so we can according to the digital is 0 or 1, elements can be divided into two groups, the same elements of binary all the same, so it is assigned to a group, or the result is 0. Different elements must be separated into two different groups, so the results of the last two xOR groups are the two elements that only appear once, and we only need to return the results of the two xOR groups

code

class Solution {
public:
    vector<int> singleNumber(vector<int> &nums) {

        
        int c(0);
        for (int i:nums) {
            c ^= i;
        }
        int tar = 1;
        for (int i = 0; i < 30; ++i) {
            if((tar & c) ! =0)
                break;
            tar <<= 1;
        }
        int a = 0, b = 0;
        for (int i:nums) {
            if ((tar & i) == 0)
                a ^= i;
            else b ^= i;
        }
        return vector<int>{a,b}; }};Copy the code
  • Time complexity: O(n), where n is the length of array NUMs.
  • Space complexity: O(1).