主页 / 问题 / 890621
Accepted
Clarence
Asked:2020-10-09 00:38:31 +0000 UTC2020-10-09 00:38:31 +0000 UTC

数组中的随机数不等于 0

  • 772

有一定的整数数组，比如[5, 0, 2, 4, 0, 0, 2, 9] 需要从这个数组中选择一个随机数，但不等于0。使用​​它random检查0直到有一个合适的数字在时间上是不合理的，理论上你几乎可以搜索无限期地。另一种选择是遍历此数组并创建一个新数组，丢弃所有零，然后random从新数组中进行选择。这也很昂贵并且需要额外的内存。还有其他类似的搜索选项吗？

python

3 个回答

  1. Best Answer

    如果数组中零的数量很大，即 使用“试错法”是不合适的，那么问题可以很容易地在一次遍历数组的情况下解决，而不需要额外的内存，即 无需创建任何新数组或修改现有数组。

    我们只是从头到尾遍历我们的数组，忽略零元素，计数非零元素，每次遇到一个非零元素，我们以概率“取”它1 / K，这里K是遇到的非零元素的个数到目前为止`。当整个数组被扫描后，最后一个“采取”的元素就是我们等可能选择的元素。

    这是一个油藏案例的经典“油藏采样”。只有在您的情况下，您才需要忽略空值。

    例如，在 C 中它可能看起来像这样

    #include <stdlib.h>
#include <stdio.h>

int main(void)
{
  const unsigned a[] = { 5, 0, 2, 4, 0, 0, 2, 9 };
  unsigned n = sizeof a / sizeof *a;

  unsigned take, nz = 0;
  for (unsigned i = 0; i < n; ++i)
    if (a[i] > 0 && rand() % ++nz == 0)
      take = a[i];

  printf("%u\n", take);
}

    当然，如果您需要对相同的输入数据多次执行这样的选择，那么简单地“过滤”一次原始数组仍然有意义，从其中排除零。

    • 3

  2. 您可以就地压缩数组

    zcount = 0
for i in range(len(A)):
     if A[i] == 0:
         zcount +=1
     else:
         A[i - zcount] = A[i]

    如有必要，将最后一个元素的 zcount 设置为零

    • 1

  3. 如果在额头上，我们找到了元素，而 0 我们继续前进到下一个。

    import random

lst = [5, 0, 2, 4, 0, 0, 2, 9]
idx = random.randrange(0, len(lst))
while not lst[idx]:
    idx += 1
    if idx > len(lst):
        idx = 0
print(idx, lst[idx])

    如果是声明性的

    from itertools import chain

lst = [5, 0, 2, 4, 0, 0, 2, 9]
idx = random.randrange(0, len(lst))
print(next(filter(bool, chain(lst[idx:], lst))))
    • 0

相关问题