寻找缺失的整数

11.寻找缺失的整数

题目

在一个无序数组里有99个不重复的正整数，范围是1100，唯独缺少一个1100的整数。然后找出这个缺失的整数。
思路

1.对无序数组，举行升序排序，先判断首位是否为2或99，如果是则得到缺失值，否则，不连续的两个元素中间即为，缺失值。时间复杂度，为排序算法的时间复杂度，空间复杂度为O(1)。代码略
2.求出无序数组的和，用1+2+...100 -和，即为缺失值。时间复杂度O(n)，空间复杂度O(1)。代码略
题目扩展1

题目

在一个无序数组里有若干个正整数，范围是1~100，其中99个整数都出现了偶数次，只有一个整数出现了奇数次，如何找到这个出现奇数次的整数？
这里，用到离散数学中的异或运算规律。

1. n为整数
2. n xor n = 0;
3. n xor 0 = n;

复制代码

思路

一个整数，与本身异或的结果一定是0，而偶数次的整数，在异或操作中都为0了，而奇数次的整数，与0异或的结果一定是其本身。
代码

1.    public static int getLostNum(int[] array){
2.        if(array.length == 1)
3.            return array[0];
4.        int first = array[0];
5.        for(int i = 1; i < array.length;i++){
6.            first ^= array[i];//Java中^(两边是数字类型)用来表示数学异或运算
7.        }
8.        return first;
9.    }
11.     public static void main(String[] args) {
12.         int[] arr = {1,1,5,5,7};
13.         System.out.println(getLostNum(arr));
14.     }

复制代码

时间复杂度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。
代码

[code]    public static int[] getLostTwoNum(int[] array) {        int[] result = new int[2];        int xorResult = 0;        for (int i = 0; i < array.length; i++)            xorResult ^= array;        if (xorResult == 0)            return null;//不符合题意        int separator = 1;        //确定2个整数的不同位，以此分组        while (0 == (xorResult & separator))            separator