寻找缺失的整数
11.寻找缺失的整数题目
在一个无序数组里有99个不重复的正整数，范围是1100，唯独缺少一个1100的整数。然后找出这个缺失的整数。
思路
1.对无序数组，举行升序排序，先判断首位是否为2或99，如果是则得到缺失值，否则，不连续的两个元素中间即为，缺失值。时间复杂度，为排序算法的时间复杂度，空间复杂度为O(1)。代码略
2.求出无序数组的和，用1+2+...100 -和，即为缺失值。时间复杂度O(n)，空间复杂度O(1)。代码略
题目扩展1
题目
在一个无序数组里有若干个正整数，范围是1~100，其中99个整数都出现了偶数次，只有一个整数出现了奇数次，如何找到这个出现奇数次的整数？
这里，用到离散数学中的异或运算规律。
n为整数
n xor n = 0;
n xor 0 = n;思路
一个整数，与本身异或的结果一定是0，而偶数次的整数，在异或操作中都为0了，而奇数次的整数，与0异或的结果一定是其本身。
代码
public static int getLostNum(int[] array){
if(array.length == 1)
return array;
int first = array;
for(int i = 1; i < array.length;i++){
first ^= array;//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。
代码
public static int[] getLostTwoNum(int[] array) { int[] result = new int; 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
页:
[1]