我有一个随机数生成器,它生成1 to k
之间的数字。此外,我有int
类型的数组(即int[]
),其大小为N
,其中k
小于N。
现在的问题是,我需要将唯一的生成数保存到数组中(拒绝生成的重复数),并且必须保持生成数的顺序,而不需要使用任何额外的空间和O(N)
的复杂性。也就是说,我同样需要保持数组中生成数的顺序。这样我就可以按生成的顺序检索它们。假设不使用位图或额外的数组等。
这不是家庭作业。这是面试中的一个问题。我不应该使用任何额外的空间。他让我使用k
比N
小的事实,并且您需要在同一数组中灌输hashmap的行为。我提出了许多使用额外空间的算法,但他拒绝也使用排序,但我无法维持生成的顺序。
好吧,我买这不是家庭作业。这是解决方案。假设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]
,你就得稍微调整一下。