保存排序中的元素的算法維護順序

Question

我有一個隨機數發生器，它生成1 to k之間的數字。我也有int類型的數組（即int[]），其大小爲N，其中k小於N.

現在的問題是我需要將唯一生成的數字保存到數組中（拒絕生成的重複數字）並且必須維護生成的數字的順序，而不使用任何額外的空間和複雜度。即我同樣的陣列我需要維護生成的數量的順序也。以便我可以按照生成的順序檢索它們。沒有位圖或額外的數組等是假設使用。

它不是一個功課。它是面試問題之一。我不應該使用任何額外的空間。他要求我使用k小於N的事實，並且您需要在同一陣列中灌輸hashmap的行爲。我提出了許多使用額外空間的算法，但他也拒絕使用排序，但我無法維持生成的順序。

Answer 1

好的，我會買這不是功課。這是解決方案。假設K = 3，N = 5

開始：

ar[0] = 0 
ar[1] = 0 
ar[2] = 0 
ar[3] = 0 
ar[4] = 0 

生成一個隨機數。假設它是2.我們需要現在存儲兩位信息：

• 「2」是第一個隨機數。
• 採取「2」。

所以我們這樣做：

ar[0] = 2 
ar[1] = 0 
ar[2] = 10 // 10 is any number that's larger than N. 
ar[3] = 0 
ar[4] = 0 

下一個數字：4

ar[0] = 2 
ar[1] = 4 
ar[2] = 10 // taken 
ar[3] = 0 
ar[4] = 10 // taken 

下一個數字：2

ar[2] >= 10 thus taken, try another number 

下一個數字：1

ar[0] = 2 
ar[1] = 14 // added 10 to signify it's taken 
ar[2] = 11 // added 1 as it's the current number 
ar[3] = 0 
ar[4] = 10 // taken 

完成。

現在，遍歷數組，並從一切比10大10減去你會

ar[0] = 2 
ar[1] = 4 
ar[2] = 1 
ar[3] = 0 
ar[4] = 0 

一個需要注意的結束 - 這是假定隨機數是[1..N]範圍。如果他們是[0..N-1]，你必須調整一下。