1. 40億個無符號整數,找出一個不在這40億個整數中的數。可以換個方向思考, 99個小于100的數,找出一個不在這99個數中的小于100的數。
首先把這99個數分為10組,按高位為0-9分,然后計算每組的數量,數量最少的那個肯定就是缺失的那個,然后遞歸……找最少的那個,組合起來的數肯定是缺失的。答案是按位運算找,和這個類似。
2. 43億個無符號整數,找出一個重復的整數。也就是101個小于100的數,找出重復的那個數來。
首先把這99個數分為10組,按高位為0-9分,然后計算每組的數量,數量最多的那組,肯定有重復的,一次類推找第二位……