[CareerCup] 10.4 Find All Duplicates Elements 寻找所有的重复项 - Grandyang - 博客园

[CareerCup] 10.4 Find All Duplicates Elements 寻找所有的重复项 - Grandyang - 博客园

[CareerCup] 10.4 Find All Duplicates Elements 寻找所有的重复项

 

10.4 You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4 kilobytes of memory available, how would you print all duplicate elements in the array?

 

这道题给了我们很多在区间[1, 32000]中的数，让我们只用4KB的内存大小来找出所有的重复项。跟之前那道题很类似10.3 Integer not Contain in the File 文件中不包含的数，还是需要用位向量Bit Vector来解，4KB内存共有2¹⁵个位Bit，大于32000个数，所以我们可以用每个bit来表示一个数，我们需要一个位向量类BitSet，来建立和数字之间的映射，有点像哈希表的功能，是一个整型数组，由于int型最大可以表示2³²，所以一个位置就可以映射2³²个数字，参见代码如下：

Read full article from [CareerCup] 10.4 Find All Duplicates Elements 寻找所有的重复项 - Grandyang - 博客园