目录
1.异或特性介绍
2.消失的数字
3数组中数字出现的次数
4. 消失的两个数字
1.异或特性介绍
异或:在二进制的表示中,两个数异或,同位上的两个数,异或,不同则为1,相同为0
如4^9
4二进制表示 0000 0000 0000 0000 0000 0000 0000 0100
9二进制表示 0000 0000 0000 0000 0000 0000 0000 1001
两者异或之后的结果是
0000 0000 0000 0000 0000 0000 0000 1101
对于异或这是一个非常重要的知识点,对于算法当中
异或的特性有,1.交换律,a^b=b^a
2.恒等性,0^a=a,即0与任何数异或之后,还是任何数,不改变这个数
2.归零性,a^a=0,即两个相同的数异或之后就变成0,
2.结合律a^b^a=b,两个相同的 数异或之后就没了
举个例子
0^3^1^8^9=3^1^8^9
3^9^7^9^7=3
2.消失的数字
消失的数字
数组
nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?注意:本题相对书上原题稍作改动
示例 1:
输入:[3,0,1] 输出:2
讯享网示例 2:
讯享网输入:[9,6,4,2,3,5,7,0,1] 输出:8
int missingNumber(int* nums, int numsSize) { int arr[numsSize]; int i=0; for(i=0;i<numsSize;i++) { arr[i]=i+1;//先把arr里面赋的是完整的1到n } int x=0; for(i=0;i<numsSize;i++) { x^=arr[i];//0和他们异或之后就是异或1^2^3……^n } for(i=0;i<numsSize;i++) { x^=nums[i];//异或之后的1^2^3……^n再和原数组进行异或,之后一样的就都没了,就只剩一个落单的,就是那个消失的数 } return x; }
3数组中数字出现的次数
一个整型数组
nums里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。示例 1:
讯享网输入:nums = [4,1,4,6] 输出:[1,6] 或 [6,1]示例 2:
输入:nums = [1,2,10,4,1,4,3,3] 输出:[2,10] 或 [10,2]限制:
2 <= nums.length <= 10000
这题运用到了分组异或的思想
讯享网 / * Note: The returned array must be malloced, assume caller calls free(). */ int* singleNumbers(int* nums, int numsSize, int* returnSize){ int ret=0; int i; //假设出现1次的数是x1和x2 //把所有数都异或 for(i=0;i<numsSize;i++) { ret^=nums[i]; } //异或完了就是剩下两个数的异或结果 //ret=x1^x2 //下一步就是想办法分离两者 //找出ret里面第m位为1的,说明x1和x2的第m位不一样,一个为1一个为0 //我们在ret里面不好分离,在原数组里面分离x1和x2 //分成两组,第m位位1的位一组 // 第m位为0的为一组 //所以x1,x2一定会分别在这两组里面 //其他数成对出现在某一组,相同的数,那一位肯定相同,肯定都在同一组 int m=0;//因为是在数组里面找第m位,所以把他弄成0 //ret一定不为0,一定有1这一位 while(m<32)//int一共有32位 { if(ret&(1<<m))//ret与上1左移m为,如果为1,就找到了那个第m位 break; else m++; } // int x1=0,x2=0; for(i=0;i<numsSize;i++) { if(nums[i]&(1<<m)) { //为1的在一组 x1^=nums[i]; } else { x2^=nums[i]; } } int* returna=(int*)malloc(sizeof(int)*2); *returnSize=2; returna[0]=x1; returna[1]=x2; return returna; }
4. 消失的两个数字
给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?
以任意顺序返回这两个数字均可。
示例 1:
输入:[1]输出: [2,3]示例 2:
讯享网输入:[2,3]输出: [1,4]提示:
nums.length <= 30000
我们上面介绍了分组异或的思想

/ * Note: The returned array must be malloced, assume caller calls free(). */ int* missingTwo(int* nums, int numsSize, int* returnSize) { int ret=0; int ret1=0; int i=1; for(i=1;i<=numsSize+2;i++) { ret^=i; } for(i=0;i<numsSize;i++) { ret^=nums[i]; } //此时ret的结果就是剩下两个数异或的结果 int m=0; while(m<32) { if(ret&(1<<m)) { break; } else m++; } int ret0=0; int ret2=0; //先分组做原数组的 for(i=0;i<numsSize;i++) { if(nums[i]&(1<<m)) { ret0^=nums[i]; } else ret2^=nums[i]; } for(i=1;i<=numsSize+2;i++) { if(i&(1<<m)) { ret0^=i; } else ret2^=i; } *returnSize=2; int *retarr=(int *)malloc(sizeof(int)*2); retarr[0]=ret0; retarr[1]=ret2; return retarr; }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76786.html