Find Duplicates
10.8 Find Duplicates: 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?
- Brainstorm:
- Given 32000 numbers each of which are 32 bit integers, we have a total of 1024000 bits of information, and insufficient 4kb = 2^12 bits = 4096 bits of memory. (250x fewer).
- Store in 500 hash tables. That contain the digits as well as the frequencies of the digits.
- Merge the hash tables with external merge sort.
- Print out frequencies stored.
- Solution:
- Bit vector.
Last modified 3yr ago