0260._Single_Number_III.md

260. Single Number III

难度:Medium

刷题内容

原题连接

• https://leetcode.com/problems/single-number-iii/

内容描述

Given an array of numbers 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.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]
Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

思路1 - 时间复杂度: O(n)- 空间复杂度: O(1)******

这题与之前的那题略有不同，这次有两个 single number，用之前的思维去做的话，在对数组进行依次异或运算之后得到的应该是两个 single number 异或值aXorb，接下来将aXorb转换成二进制，从第0位找起，第一个为1的位，则说明在这个位上a 和 b不相等，把数组中的数分成两部分，即在这个位上为0的一部分，为1的一部分，这样就把两个数分到了不同的两部分中。接着分别对这两部分异或就能得到结果

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int aXorB = 0;
        for (int num : nums) {
            aXorB ^= num;
        }
        int differingBit = 1;
        while ((differingBit & aXorB) == 0) {
            differingBit <<= 1;
        }
        int a = 0;
        int b = 0;
        for (int num : nums) {
            if ((num & differingBit) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return {a, b};
    }
};