目录
消失的数字
方法1
方法2
方法3
找单身狗
消失的数字
题目如下：
方法1
方法1的思想是先将给定的数组排序，然后查看从哪个下标开始，下标和对于位置元素的值不同，那么消失的数字就是那个下标
但是在常见的排序算法中，最快的快排的时间复杂度是O(n*logn)，所以不符合题意
方法2
可以看出，给定数组其实就是一个等差为1的等差数列中缺少一个数字
所以我们可以计算出这个等差数列的和，再一次减去给定数组中每个元素的值，最后剩下的值就是消失的数字。
代码如下：
int missingNumber(int* nums, int numsSize) { int sum = numsSize * (numsSize + 1) / 2; for (int i = 0; i < numsSize; i++) { sum = sum - nums[i]; } return sum; }
方法3
方法3的思想是运用位操作符中的按位异或^
按位异或的一些特点：
1.对应的二进制位：相同位0，相异为1
2.a^a = 0
3.a^0 = a
4.异或支持交换律
所以我们可以将给定数组中的每个元素进行按位异或操作，然后再与一个[0,numsSize]数组中每个元素进行按位异或，最终得到的值就是消失的数字
代码如下：
int missingNumber(int* nums, int numsSize) { int n = 0; for (int i = 0; i < numsSize; i++) { n ^= nums[i]; } for (int i = 0; i <= numsSize; i++) { n ^= i; } return n; }
找单身狗
上一道题最主要最有意思的做法就是运行按位异或计算
下面也是一道有关按位异或运算的题：
一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
根据上一题的思想，我们可以将两个单独的数字分到不同“组”中，再将两个“组”中的每个数字进行按位异或，最后得到2个单身狗
以数组[1,2,3,4,5,1,2,3,4,6]为例：
将这些数字都按位异或 1^2^3^4^5^1^2^3^4^6，最终可以得到5^6
5的二进制是 0101
6的二进制是 0110
5^6的值位为0011
以下是将数组元素依次异或的代码：
void singal_dog(int* nums, int size, int* singal_arr) { int val = 0; for (int i = 0; i < size; i++) { val ^= nums[i]; } }
我们可以根据某些特点，将元素分为2组，例如二进制最后一位数字是否为0，或是否为1
所以 以最后一位数字是否为0进行分组，为0分一组，不是0分一组：
可以看到将这2组依次进行按位异或就可以得到单生狗
那么怎么能知道这个数组中的数字是从哪位开始有区别的呢？
答案就是通过之前的 5^6的值得知
5^6的值位为0011，因为是按位异或，所以那位值为1，哪位就不同
所以可以看到，这一组数字就可以通过最后一位数字来分组
下面是找到有区别可以分组的那一位数字的代码：
void singal_dog(int* nums, int size, int* singal_arr) { int pos = 0; for (int i = 0; i < 32; i++) { if (((val >> i) & 1) == 1) { pos = i; break; } } } 1
最后，将2组代码依次按位异或，就可以得到单身狗
下面是完整代码：
void singal_dog(int* nums, int size, int* singal_arr) { int val = 0; for (int i = 0; i < size; i++) { val ^= nums[i]; } int pos = 0; for (int i = 0; i < 32; i++) { if (((val >> i) & 1) == 1) { pos = i; break; } } for (int i = 0; i < size; i++) { if (((nums[i] >> pos)&1) == 1) { singal_arr[0] ^= nums[i]; } else { singal_arr[1] ^= nums[i]; } } } int main() { int arr[] = { 1,2,3,4,1,2,3,4,5,6 }; int sz = sizeof(arr) / sizeof(arr[0]); int singal[2] = { 0 }; singal_dog(arr, sz,singal); printf("%d %d", singal[0], singal[1]); return 0; }
