1. 40亿个无符号整数,找出一个不在这40亿个整数中的数。可以换个方向思考, 99个小于100的数,找出一个不在这99个数中的小于100的数。
首先把这99个数分为10组,按高位为0-9分,然后计算每组的数量,数量最少的那个肯定就是缺失的那个,然后递归……找最少的那个,组合起来的数肯定是缺失的。答案是按位运算找,和这个类似。
2. 43亿个无符号整数,找出一个重复的整数。也就是101个小于100的数,找出重复的那个数来。
首先把这99个数分为10组,按高位为0-9分,然后计算每组的数量,数量最多的那组,肯定有重复的,一次类推找第二位……