0

我试图找到一种合理有效的方法来获取不在集合中的任何单个整数。因此，例如，如果我有numbers={1, 4, 9}，那么有效的结果将是3。我可以这样做：

n = random.randint(-100, 100)
if n not in numbers:
    return n

但我不想被限制在任意范围内（例如 -100 -> 100），因为我不知道该集合有多大。另一种选择是遍历每个整数，但这将非常低效。

有没有人对这样做的更好方法有任何建议？

编辑：由于关于我正在尝试做什么的问题很多，我正在更新这个问题以解释一些背景。

我实际上想要实现的是这样的映射：where 和{a: 1, b: 2, c: 1}是a对象实例。这个值是一个组的唯一值，所以我可以告诉它，并且在第 1 组和第 2 组中。实际数字无关紧要，它只是组的唯一键，与此结构之外的任何内容都无关。实际结构是一个包含两个字段的数据库表，这两个字段都已编入索引，以便我可以快速找出，例如，与.bcacba

现在我需要唯一的号码，是当我想添加一个组时。这不会经常发生，因此它不必非常高效，但由于数据量可能会变得非常大，我需要降低迭代次数。我意识到有一些简单的方法可以在可接受的限制下执行此操作，例如使用randint大范围（例如 1e6），或者甚至可能使用数据库函数。但是，由于我一直在考虑这一点，因此找到一个巧妙的解决方案来填充没有硬编码限制的值已成为一个有趣的问题。显然内存限制（例如整数的最大大小）仍然适用。

4

5 回答 5

2

怎么样max(numbers)+1？

于 2012-04-05T09:03:12.217 回答
2

不在集合中的任何单个整数

但是有无限个整数值，所以有无限个整数值不在有限集中。除非您在谈论有限范围内的整数（例如 16 位）。

最有效的解决方案将取决于整数集的完整性 - 如果它是稀疏的，那么随机选择一个数字可能会更频繁地返回一个不在集合中的数字。如果差距很少，那么优化的搜索将更有效。这两者都依赖于对集合的排序列表。

查看搜索方法，可以通过对数据进行分区来加快搜索速度：计算列表中数字的最低和最高索引的平均值 M，如果 dataset[M]<(M-dataset[0]) 那么有间隙，否则检查 dataset[last]<(dataset[0]+last) 在这种情况下，后半部分有间隙，对有间隙的一半数据重复该过程。

于 2012-04-05T09:30:41.970 回答
0 
def numnotinset(myset):
  i = min(myset)
  while True:
    i += 1
    if not i in myset:
      return i
于 2012-04-05T09:03:27.017 回答
0

不完全确定您需要什么

>>> numbers = {1, 4, 9}
>>> from itertools import count
>>> next(x for x in count() if x not in numbers)
0
于 2012-04-05T09:33:42.490 回答
0

不，它可以是任何数字。我基本上是在尝试生成要在字典中使用的键。

听起来像一个XY 问题。

为什么要用随机数键入字典？你甚至应该使用字典吗？

如果您需要数字索引，对于字典，最简单的方法是记录给出的最后一个键，然后当您需要另一个键时，增加这个数字并使用它。

您忽略了因删除和/或偶尔重新编号而导致索引丢失的问题。

于 2012-04-05T11:27:53.217 回答