2025年异或的高级用法以及LeetCode刷题

异或的高级用法以及LeetCode刷题目录 1 异或特性介绍 2 消失的数字 3 数组中数字出现的次数 4 消失的两个数字 1 异或特性介绍 异或 在二进制的表示中 两个数异或 同位上的两个数 异或 不同则为 1 相同为 0 如 4 9 4 二进制表示 0000 0000 0000

大家好,我是讯享网,很高兴认识大家。

目录

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; } ​
小讯
上一篇 2025-02-16 13:34
下一篇 2025-03-21 21:06

相关推荐

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