寻找缺失的整数

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)。

只是为了记录自己的学习历程，且本人水平有限，不对之处，请指正。