Cracking Coding Interview - 10.8 Find Duplicates

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?

Hints: #289, #315

解法

又遇到了有限内存的问题。

题目中给了4K内存，4K = 4096 bytes = 8 * 4096 bits => 32,000 。题目中由说了N不会超过32,000，那也就意味着我们可以用bit vector来做这个事情。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


public int findDuplicates(int[] array) {
  byte[] bitVector = new byte[4 * 1024];
  for (int i = 0; i < array.length; i++) {
    int byteIndex = i / Byte.SIZE;
    int bitIndex = i % Byte.SIZE;
    byte flag = 1 << bitIndex;
    if (bitVector[byteIndex] & flag == 0) {
      bitVector[byteIndex] |= flag;
    } else {
      System.out.println(i);
    }
  }
}

Cracking Coding Interview - 10.8 Find Duplicates

解法

版权

评论

Cracking Coding Interview - 10.8 Find Duplicates

解法

版权

相关文章

评论