企业网站建设英文,网站建设推广的话术,腾讯网微信公众平台,三水网站建设哪家好题目#xff1a;
给你一个整数数组 nums#xff0c;其中恰好有两个元素只出现一次#xff0c;其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1…题目
给你一个整数数组 nums其中恰好有两个元素只出现一次其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。 示例 1
输入nums [1,2,1,3,2,5]
输出[3,5]
解释[5, 3] 也是有效的答案。示例 2
输入nums [-1,0]
输出[-1,0]示例 3
输入nums [0,1]
输出[1,0]提示
2 nums.length 3 * 104-231 nums[i] 231 - 1除两个只出现一次的整数外nums 中的其他数字都出现两次
思路
1 所有数字异或结果是只出现一次的两个数字的异或结果 异或相同为0相异为10与任何数异或都是数字本身
2 得到答案的两个数字异或的结果区分这两个数字 这两个数字互不相同则一定在某些二进制位上一个数字是1另一个数字则对应是0
异或的结果它所有的二进制位中一定存在二进制位为1的此位置的二进制位就可以区分
a 在异或结果中找到一个可以区分两个数字的二进制位 数字(-数字可以得到此数字二进制位中最低位的1这里称之为j 那么异或结果(-异或结果就是异或结果二进制位中最低位的1
注意若异或结果是INT_MIN即-2147483648 原码 1000 0000 0000 0000 0000 0000 0000 0000 用于位运算的补码溢出了 所以当异或结果为INT_MIN时异或结果本身就是最低位的1不用进行位运算
INT_MAX :0111 1111 1111 1111 1111 1111 1111 1111
-INT_MAX的补码1000 0000 0000 0000 0000 0000 0000 0001
都没有溢出所以INT_MAX是可以进行位运算来获取INT_MAX二进制中最低位的1
如3 00000000 00000000 00000000 00000011整数的原码反码补码都相同 -3的原码 10000000 00000000 00000000 00000011位运算都要用补码 -3的反码 11111111 11111111 11111111 11111100原码的符号位不变其他位按位取反 -3的补码 11111111 11111111 11111111 11111101补码1
3-300000000 00000000 00000000 00000011 11111111 11111111 11111111 11111101
结果 00000000 00000000 00000000 000000013最低位的那个1
再如 b 根据j将所有数字划分成两个阵营分别异或在一起 出现两次的数字一定在同一阵营异或一定为0 某数字j为1表示此数字在作为区分的二进制位上数值为1 某数字j为0表示此数字在作为区分的二进制位上数值为0 最终两阵营的结果就是两个答案了
代码实现
class Solution
{
public:vectorint singleNumber(vectorint nums){int k 0;//所有数字异或的结果for(auto e:nums){k^e;}int j kINT_MIN?k: k(-k);//异或结果二进制中最低位的1int ret1 0;int ret2 0;for(auto e:nums){if(ej)//在作为区分的二进制上数值为1{ret1^e;}else在作为区分的二进制上数值为0{ret2^e;}}return {ret1,ret2};}
};
