11.寻找缺失的整数
题目
在一个无序数组里有99个不重复的正整数，范围是1100，唯独缺少一个1100的整数。然后找出这个缺失的整数。
思路
1.对无序数组，进行升序排序，先判断首位是否为2或99，如果是则得到缺失值，否则，不连续的两个元素中间即为，缺失值。时间复杂度，为排序算法的时间复杂度，空间复杂度为O(1)。代码略
2.求出无序数组的和，用1+2+...100 -和，即为缺失值。时间复杂度O(n)，空间复杂度O(1)。代码略
题目扩展1
题目
在一个无序数组里有若干个正整数，范围是1~100，其中99个整数都出现了偶数次，只有一个整数出现了奇数次，如何找到这个出现奇数次的整数？
这里，用到离散数学中的异或运算规律。
```txt
n为整数
n xor n = 0;
n xor 0 = n;
```
思路
一个整数，与本身异或的结果一定是0，而偶数次的整数，在异或操作中都为0了，而奇数次的整数，与0异或的结果一定是其本身。
代码
```java
public static int getLostNum(int[] array){
if(array.length == 1)
return array[0];
int first = array[0];
for(int i = 1; i < array.length;i++){
first ^= array[i];//Java中^(两边是数字类型)用来表示数学异或运算
}
return first;
}
public static void main(String[] args) {
int[] arr = {1,1,5,5,7};
System.out.println(getLostNum(arr));
}
```
时间复杂度O(n)，空间复杂度O(1)。
题目扩展2
题目
假设一个无序数组里有若干个正整数，范围是1~100，其中有98个整数出现了偶数次，只有2个整数出现了奇数次，如何找到2个出现奇数次的整数？
思路
按照扩展1的逻辑，则题目2中无序数组，依次异或的结果，一定是，出现奇数次的结果result = A xor B。并且这个，结果一定是不等于0的，因为如果等于0了，就代表这两个数相同了，不符合题意。如何根据这个!=0的异或结果，求出这两个值呢？result不等于0，代表结果的补码中，一定至少有一位的值为1，代表，在这一位，A和B的补码，一定一个是1一个是0，就可以利用这个特性，将原数组，分为两个子数组，且A和B一定会分到两个数组中，再利用扩展1的思路，分别独立进行异或运算，两个子数组的结果，就是A和B。
代码
```java
public static int[] getLostTwoNum(int[] array) {
int[] result = new int[2];
int xorResult = 0;
for (int i = 0; i < array.length; i++)
xorResult ^= array[i];
if (xorResult == 0)
return null;//不符合题意
int separator = 1;
//确定2个整数的不同位，以此分组
while (0 == (xorResult & separator))
separator <<= 1;//算术左移
//经过while循环后，separator的值，为xorResult中从右往左第一个不为0的位所代表的值
for(int i = 0; i < array.length; i++){
//分为两组
if(0 == (array[i] & separator))//代表对应位为0
result[0] ^= array[i];
else//代表对应位为1
result[1] ^= array[i];
}
return result;
}
```
时间复杂度O(n)，空间复杂度O(1)。
只是为了记录自己的学习历程，且本人水平有限，不对之处，请指正。
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/6442.html
