java - 在数组中保存元素的算法保持顺序

Question

我有一个随机数生成器，它生成 1 到 k 之间的数字。我还有 int 类型的数组(即 int[])，其大小为 N，其中 k 是小于 N 。

现在的问题是我需要将生成的唯一数字保存到数组中(拒绝生成的重复数字)并且必须保持生成数字的顺序，而不使用任何额外空间并且复杂度为 O(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] ，你必须稍微调整一下。