在数组维护顺序中保存元素的算法

Question

我有一个随机数生成器,它生成之间的数字1 to k.我也有int类型(ie 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.我们现在需要存储两位信息:

所以我们这样做:

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],你必须调整一下.