整数分为有符号和无符号两种，有符号数的取值为-2147483648~2147483648 是从-21亿到+21亿， 无符号数的范围为0~4294967296是从0到42亿，然而给了我们100亿个整数，要找出只出现一次的整数，所以我们还是要用到哈希表的思想，但我们最好不要定义一个整型数组，因为 42亿*4B 约为16G，这么大的数组我们再进行切分的话就太麻烦了，这里我们可以使用BitMap,用一个位来表示一个数存不存在，不存在表示为0，出现一次表示为1，出现一次以上用另一个位表示。这样就可以将数组的大小减为原来的16分之一。还遇到一个问题，就是到底怎么定义这个数组，正数好定义，负数的话我们可以用32位全1（-1）和它取异或取到和正数相同的位置，我们此时定义一个二维数组，一半表示正数一半表示负数，都位于同一行。此时我们使用1G的空间就可以解决这个问题了。
标签： 符号、正数、亿个、整数、负数、面试
猜你感兴趣的圈子：
