algorithm - 这个问题最有效的算法

Question

问题：假设我有一个大小为 N 的数组，范围为 [1, N]。我想生成一个随机数 k，使得 1 <= k <= N，并用随机字母占据 arr[k]。我会得到另一个随机数 p，它与 k 不同，随机占据那个槽。我会一遍又一遍地重复这个，直到没有空位。此外，这些随机生成的字母中的一个可能会从它们先前占用的位置中删除。

这里的问题是，每次我选择一个新数字时，我都很难猜出一个尚未被占用的随机数。

我正在尝试为这个问题找到解决方案，显然是以最有效的方式（空间和复杂性）。

我提出了几种解决方案，但我认为它们效率不高，而且我很难计算它们的复杂性。

计划 A) 对于我在 [1, N] 范围内随机选择的每个整数，我检查它是否被占用。如果是，我重新滚动，直到我得到一个未被占用的。这在 N 的高阶时变得低效，因为冲突非常高。

计划 B）对于每次迭代，我都会检查数组的所有值，那些我不占用的值我会写在一个列表中。之后，我对列表进行洗牌（例如通过 Fisher-Yates 洗牌？）并任意获得第一个对象。这不节省空间，对于我的问题，我不能只保留一个列表并从那里随机播放，因为在我的程序中可能有多个线程计算这个。

方案C）方案A的小改动：我在[1，N]范围内随机选择，我检查它是否被占用。如果是，我 +1 并尝试下一个，如果是，再次 +1。最坏的情况是所有阵列槽都被占用，除了一个 -> O(N)。

有没有更好的方法来解决这个问题？这个特定问题是我软件中一个非常重要的模块，因此时间复杂度至关重要。如果没有，您认为我应该采用哪种方式（对于那些有计算时间复杂度的人才）。谢谢！

标签： algorithmtime-complexitycomputer-science

Answer 1

我建议您同时使用计划 A 和 B。

使用 A 直到数组大部分被填满。然后搜索未使用的索引，将它们放入一个数组中，然后使用 B 计划。您将不得不试验您的约束以确定何时切换。

不过，您对多个线程执行此操作的评论令人担忧。请注意，当多个线程访问同一内存时，竞争条件很容易，访问争用会减慢您的速度。