Find duplicate integer in an large integer array | Hello World
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 4KB of memory available, how would you print all duplicate elements in the array?
4KB memory = 4*8*2^10 bits, which is larger than the 32000, so we can map each integer to one bit and count the duplicates.
The java only support granularity of bytes, so in order to do bit operation, we need to implement bitSet of our own. Here is a sample of implementation, the divide operation could be replaced by bitshift operation.
Read full article from Find duplicate integer in an large integer array | Hello World
No comments:
Post a Comment