arrays - 无冲突随机填充数组的算法

Question

假设我将一个包含 N 个整数的数组设置为值“0”，我想从该数组中选择一个值为“0”的随机元素并将其设为值“1”

我如何有效地做到这一点？

我想出了 2 个解决方案，但它们看起来很低效

第一个解决方案

int array[N] //init to 0s
int n //number of 1s we want to add to the array
int i = 0
while i < n
    int a = random(0, N)
    if array[a] == 0
        array[a] = 1
        i++
    end if
end while

由于碰撞的可能性，对于大型阵列来说效率极低

第二个涉及一个包含所有剩余 0 位置的列表，我们选择一个介于 0 和剩余 0 的数量之间的随机数来查找列表中与数组中的索引对应的值。它比第一个解决方案可靠得多，因为操作的数量是有限的，但如果我们想完全填充数组，最坏情况下的复杂度仍然是 N²

Answer 1

您的第二个解决方案实际上是一个好的开始。我假设它涉及在每次更改后重建位置列表，如果您想填充整个数组，这将使其成为 O(N²)。但是，您不需要每次都重建列表。由于您无论如何都想填充数组，因此您可以只使用随机顺序并相应地选择剩余位置。

例如，采用以下数组(大小为 7 且最初未全为零):[0, 0, 1, 0, 1, 1, 0]

建立零位置列表后，此处为 [0, 1, 3, 6]，只需将其打乱即可获得随机排序。然后按照位置给出的顺序填充数组。

例如，如果 shuffle 给出 [3, 1, 6, 0]，那么您可以像这样填充数组:

[0, 0, 1, 0, 1, 1, 0]  <- initial configuration
[0, 0, 1, 1, 1, 1, 0]  <- First, position 3
[0, 1, 1, 1, 1, 1, 0]  <- Second, position 1
[0, 1, 1, 1, 1, 1, 1]  <- etc.
[1, 1, 1, 1, 1, 1, 1]

如果数组最初是用零填充的，那就更容易了。您的初始列表是从 0 到 N(数组的大小)的整数列表。将其打乱并应用相同的过程。

如果你不想填充整个数组，你仍然需要构建整个列表，但你可以在打乱后截断它(这意味着在某个点后停止填充数组)。

当然，这个解决方案要求数组在每一步之间不发生变化。