查找内存有限的重复元素

Question

以下是 Cracking the coding 采访中的一个问题：

You have an array with all 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?

方法签名是

public static void checkDuplicates(int[] array)

然后解决方案解释了如何使用位向量通过将每个整数表示为位来解决此问题。我的困惑是当我们运行这个方法时，它不会加载整个内存中的数组来循环它吗？现在，如果 array 的大小比方说 10 亿（很多重复的元素），这个程序不会失败，因为它将整个数组加载到内存中，而我们拥有的内存是 32 * 2^10 位？

Answer 1

这可能是一个棘手的问题。我最近在 Google 接受采访，他们有一些像你这样的问题。我认为在这些情况下最好的做法是解释您的思路并涵盖每种情况。这些问题也是人为构造的，所以他们可能漏掉了一个词等。如果我必须回答这个问题，我会想出多个答案：

所有内存使用量可能为 4KB（问题等）
您的解决方案应该适合 4KB（提到的解决方案）

文中说：

With only 4KB of memory available [...]

因为 Java 是 terms of passing values 中的一门有趣的语言，所以在将其传递给方法时，您不会创建 int 数组的新实例。

public class Test {
    public static void main(String[] args) {
        int[] stuff = {1};
        System.out.println("before: " + stuff[0]);
        doStuff(stuff);
        System.out.println("after: " + stuff[0]);
    }
    public static void doStuff(int[] array){
        array[0]=10;
    }
}

由于这种行为，您的 4KB 可用于您的内部处理算法。我认为这个限制只是为了防止 "I make a copy of it and..." 种解决方案。

Answer 2

4Ko 似乎是函数允许的内存量而不是整个程序，甚至不是，在这种情况下将内存内容交换到文件中可能非常有用 look here。

Answer 3

意思是“4KB 用于完成任务”，因此您的代码并不意味着占用更多 space。这是我脑子里想出来但还没有测试过的代码。

基本上只是使用数字的值作为位向量中的索引。如果已经设置，则打印消息；否则设置它。

public class BitVectorMagic {
    static public void checkDuplicates(final int[] pArray) {
        final int neededBytes = (pArray.length / 8) + 1;
        final byte[] bitVector = new byte[neededBytes];

        for (int i = 0; i < pArray.length; i++) {
            final int value = pArray[i];
            final int byteIndex = value / 8;
            final int indexInByte = value % 8;

            final byte bitByte = bitVector[byteIndex];
            final byte bit = getBit(bitByte, indexInByte);
            if (bit > 0) {
                System.out.println("Duplicate value " + value + " at pos " + i);
            } else {
                final byte writeBitByte = setBit(bitByte, indexInByte);
                bitVector[byteIndex] = writeBitByte;
            }
        }
    }


    private static byte setBit(final byte pBitByte, final int pIndexInByte) {
        final byte or = (byte) (0x01 << pIndexInByte);
        return (byte) (pBitByte | or);
    }


    static private byte getBit(final int pByte, final int pIndexInByte) {
        return (byte) ((pByte >> pIndexInByte) & 1);
    }
}

Answer 4

题意是32000 (possible values) / 8 (bit in byte) = 4000 ~ 4096 (4 KB).

不计算初始数组内存，因为对其大小没有合理的限制，因为给定的复制次数没有限制。

4 KB 是该方法可以使用的内存量，并且由于该方法接收指向输入数组的指针（无需复制其值），因此不计算数组大小。

据我所知，任何 O(N) 内存估计都占额外内存算法可以用来解决问题。

Answer 5

下面是经过测试的代码：

public void checkDuplicates(int[] nums){
    int bytesNeeded = (nums.length/8) + 1;
    byte[] bitSet = new byte[bytesNeeded];

    for(int i=0; i<nums.length; i++){
        int n = nums[i];
        int byteIndex = n / 8;
        int indexInByte = n % 8;

        byte bit = (byte)(bitSet[byteIndex] & (1 << indexInByte));
        if(bit > 0){
            System.out.print(nums[i] + " ");
        }else{
            bitSet[byteIndex] |= 1 << indexInByte; 
        }
    }
}

查找内存有限的重复元素

Finding duplicate elements with limited memory

java

memory

arrays

scalability