查找重複的元素具有有限內存

您有從1到N，其中N是最 32000所有的數字數組。數組可能有重複的條目，並且您不知道N是什麼。只有4KB的可用內存，您將如何在數組中打印所有重複的元素？

方法簽名是

public static void checkDuplicates(int[] array)

然後將溶液解釋瞭如何使用位向量由表示每個整數作爲位來解決這一點。我的困惑是當我們運行這個方法時，它不會加載整個內存中的數組來循環它嗎？現在如果array的大小比如說是10億（很多重複的元素），那麼這個程序就不會失敗，因爲它將整個數組加載到內存中，我們擁有的內存是32 * 2^10位？

來源

2016-07-24 Kode

我認爲這個問題詢問4KB _additional_到什麼已使用的陣列。儘管我會說沒有時間限制，但即使在恆定的空間中，也應該可以這樣做，因爲您可以重複循環數組，並使用O（32k * n）時間對從1到32k的每個數進行計數。 –

但問題顯示「只有4KB的內存可用」！我同意它可以在恆定的空間中解決，但對於給定的問題陳述，解決方案只適用於數組大小爲2^10 – Kode

@tobias_k我同意tobias。 –

這可能是一個棘手的問題。我最近在Google採訪過，他們有類似你的問題。我認爲最好在這些案例中解釋你的思路，並涵蓋每個案例。這些問題是由人類建造過，所以有可能是他們錯過了一個字等等。如果一定要我回答這個問題，我會拿出多個答案：

所有的內存使用情況可能是4KB（問題等）
您的解決方案應適合4KB（所提到的解決方案）

文說：

在只有可用的內存4KB [...]

由於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可用於您的內部處理算法。我認爲這種限制只是爲了防止「我製作它的副本......」類解決方案。

來源

2016-08-04 09:20:58 Mark

對於功能而言，4Ko似乎不是整個程序所允許的內存量，甚至不是，在這種情況下，將內存內容交換到文件中可能會非常有幫助look here。

來源

2016-08-04 13:46:48 whyn0t

意思是「4KB完成任務」，所以你的代碼並不打算佔用更多的空間。這裏的代碼是在我腦海中編寫的，但沒有經過測試。

基本上只是使用數字的值作爲位向量中的索引。如果已經設置，打印信息;否則設置它。

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); 
    } 
}

來源

2016-08-07 09:40:55 JayC667

問題的想法是，32000 (possible values)/8 (bit in byte) = 4000 ~ 4096 (4 KB)。

初始數組內存不被計數，因爲沒有對其大小進行合理的限制，因爲沒有給出複製次數的限制。

4 KB是該方法可以使用的內存量，並且由於該方法接收到指向輸入數組的指針（不需要複製其值），因此不計算數組大小。

據我所知，任何O(N)內存估計佔多餘內存算法可以用來解決這個問題。

來源

2016-08-07 16:27:06 abragin

下面是測試代碼：

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; 
     } 
    } 
}

來源

2017-03-15 05:23:27

查找重複的元素具有有限內存

回答

相關問題