目录
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int missingNumber(int* nums, int numsSize)
{
int arr[numsSize];
int i=0;
for(i=0;i<numsSize;i++)
{
arr[i]=i+1;
}
int x=0;
for(i=0;i<numsSize;i++)
{
x^=arr[i];
}
for(i=0;i<numsSize;i++)
{
x^=nums[i];
}
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
这题运用到了分组异或的思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
/**
* 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]
提示：
我们上面介绍了分组异或的思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
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];
}
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;
}
|