如何找到未列出或缺失的数字？

Question

我将会有一列数字，每个数字占据单独的一行（比如0-100）。我该如何找到没有被列出或者缺失的数字？

- curious1

---

你有重复的数字吗？它们是排序的吗？这是作业吗？ :-) - juanchopanza

Answer 1

将它们全部添加到一个集合中。然后从填充了1-100的集合中减去。这是0-9的示例：

>>> set(range(10)) - set([1, 4, 5, 6, 8, 2])
set([0, 9, 3, 7])
>>> 

我有一个列表 [1, 4, 5, 6, 8, 2]，想要查找 0-9 范围内缺失的数字。我创建了一个包含 0-9 所有数字的集合，并从中减去[1, 4, 5, 6, 8, 2] 的集合，发现 [0, 9, 3, 7] 缺失了。

使用集合来解决这个问题非常有效。此外，集合可以优雅地处理重复数据。

- Eli Bendersky

---

这是一个非常优美的解决方案。 - Chetan

不会有重复的数字，并且它们将会被排序。不，这不是作业 :) - curious1

如果需要输出排序，只需将集合转储到已排序的列表中。 - Eli Bendersky

@curious1 那么这可能是你能得到的最好的答案，尽管在这里排序是无关紧要的。 - juanchopanza

@juanchopanza：我想它可能会更高效一些，因为集合构造函数接受一个可迭代对象。然而，除非大小很大（绝对不是在1-100之间），否则我不认为会感觉到差异。 - Eli Bendersky

Answer 2

如果L是数字列表，则

set(L).difference(xrange(101))

避免从xrange创建一个集合

In [1]: L=[1, 4, 5, 6, 8, 2]

In [2]: timeit set(range(101)) - set(L)
10000 loops, best of 3: 21.7 µs per loop

In [3]: timeit set(L).symmetric_difference(range(101))
100000 loops, best of 3: 14.2 µs per loop

In [4]: timeit set(L).difference(range(101))
100000 loops, best of 3: 9.73 µs per loop

- John La Rooy

---

你也可以使用difference，symmetric_difference本质上是一个XOR。 - Eli Bendersky

Answer 3

这是一个使用关联数组（键-值）的 awk 解决方案：

printf '%s\n' 1 4 5 6 8 2 |
awk -F " " -v first=0 -v last=9 '
BEGIN { 
  for(i=first; i<=last; i++) 
    array[i] = 0
}
{
  for(i=1;i<=NF;i++)
    array[$i] += 1
}
END {
  for (num in array)
    if (array[num] == 0) print num
}
'

• 首先，我们创建一个数组，其中包含给定范围内的所有数字作为单个键，并设置默认值为0。
• 然后，每个输入数字都会被awk处理为数组的键，以便将其值递增1。
• 最后，只有那些未被递增的键被打印出来，即具有值为0的键（因为它们在数字输入范围内缺失）。

- carlo

Answer 4

bash：

# first set up an array containing the whole range
declare -a nums
for i in {0..100}; do
  nums[$i]=1
done

# then read the file and remove the numbers from it
while read number; do
  unset nums[$number]
done < file.with.numbers

# the remaining array keys are the numbers not found in the file
for number in "${!nums[@]}"; do
  echo $number
done

- glenn jackman