题目描述:
一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。
要求时间复杂度是O(n),空间复杂度是O(1)。
设 nums=[3,3,4,4,1] ,以上计算流程如下图所示。
本题难点: 数组 nums 有 两个 只出现一次的数字,因此无法通过异或直接得到这两个数字。
while(z & m == 0) // m 循环左移一位,直到 z & m != 0 m <<= 1
for(int num: nums) { if((num & m) != 0) x ^= num; // 若 num & m != 0 , 划分至子数组 1 ,执行遍历异或 else y ^= num; // 若 num & m == 0 , 划分至子数组 2 ,执行遍历异或 } return new int[] {x, y}; // 遍历异或完毕,返回只出现一次的数字 x 和 y
class Solution{ public int [] singleNumbers(int nums[]){ int x=0,y=0,n=0,m=1; for(int num:nums){// 1. 遍历异或 n^=num; } while((n&m)==0){// 2. 循环左移,计算 m m<<=1; } for(int num:nums){// 3. 遍历 nums 分组 if((num&m)!=0) x^=num;// 4. 当 num & m != 0 else y^=num;// 4. 当 num & m == 0 } return new int[]{x,y};// 5. 返回出现一次的数字 } }
注:
1、&(按位与)运算操作符,在计算机底层计算的原理中,相同位置的二进制序列进行对比,只要有0就是0,两个都是1才是1。
2、|(按位或)运算操作符,在计算机底层计算的原理中,相同位置的二进制序列进行对比,只要有1就是1,两个都是0才是0。
3、^(按位异或)运算操作符,在计算机底层计算的原理中,相同位置的二进制序列进行对比,相同为0,相异为1。
4.^=:两个二进制的对应位相同,结果为0,否则结果为1。a^=b 等效于 a=a^b 按位异或并赋值。
标签:数字,nums,Offer,int,56,异或,num,数组 From: https://www.cnblogs.com/zhz123567/p/17428499.html