在整形数组中找到只出现一次的两个整数

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。

请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

代码:

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int a=0,b=0,c=0,d=1;
        for(int i=0;i<nums.size();i++)//通过异或找到只出现一次的两个整数的异或结果 
        {
            a^=nums[i];
        }
        while((a&d)==0)//两个不同数字至少有一个二进制位不同,而那个二进制位的
        {              //异或结果为1,所以找到那个二进制位为1,其余为0的整数 
            d<<=1;    // 
        }
        for(int i=0;i<nums.size();i++)
        {
            if((nums[i]&d)==0)//以该二进制位将原数组分为两组,最后异或的结果也就是原来的两个整数了 
            {
                b^=nums[i];
            }
            else
            {
                c^=nums[i];
            }
        }
        vector<int> v;
        v.push_back(b);
        v.push_back(c);
        return v;
    }
};

类似的,比如

定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?

以任意顺序返回这两个数字均可。

输入: [2,3]
输出: [1,4]

都是稍微变化了一些,还是通过异或就可以解决了。

上一篇:PHP:类(class)和接口(interface)


下一篇:sed匹配引用和子表达式