如何从列表中找到缺失的数字？

Question

如何从列表中找到缺失的数字？

21

如何以Pythonic的方式从已排序列表中找到缺失的数字？

a=[1,2,3,4,5,7,8,9,10]

我看到了这篇帖子，但是否有更高效的方法来做这件事？

- Rajeev

1

这个问题有一个泛化版本！参考问题：https://dev59.com/dXA75IYBdhLWcg3wDUq2 - Sreejith Menon

19个回答

16

应该可以正常工作：

a = [1, 3, 4, 5, 7, 8, 9, 10]
b = [x for x in range(a[0], a[-1] + 1)]
a = set(a)
print(list(a ^ set(b)))
>>> [2, 6]

- Samman Thapa

1

优雅的解决方案，不涉及额外的模块（这是@Abhijit提供的解决方案的情况）。唯一的问题（不确定是否存在！）是转换为集合。如果列表已经包含唯一的数字，则不确定在应用set()转换时会产生什么性能影响。遗憾的是，^运算符只适用于集合，因此即使知道列表实际上是一个集合（尽管存储为列表），也需要进行转换。 - rbaleksandar

@rbaleksandar 我相信集合允许我们执行两个“列表”之间的对称差异。 - JMortey

抱歉这么晚才回复你的答案。想问一下，为什么在range中最后一个元素需要加上1的值呢？我尝试了不加1的情况，但是还是得到了相同的答案。 - dissidia

@dissidia range(0,10) 只包括从0到9（含）的值。为了也包括10，需要将a的最后一个值加1。当然，这并不重要，因为如果a中缺少10，我们怎么会知道呢？ - Raketenolli

8

1 + 2 + 3 + ... + (n - 1) + n = (n) * (n + 1)/2

所以缺失的数字是：

(a[-1] * (a[-1] + 1))/2 - sum(a)

- Gabriel

你的答案是正确的，但考虑到你的第一句话，如果你在答案中实际使用这个事实会更有意义，即删除第一部分并用该产品替换它。 - Steve P.

修改为与手头问题相关的内容。 - Steve P.

7

set(range(a[len(a)-1])[1:]) - set(a)

取所有数字的集合减去给定的集合。

- Saša Šijak

range(a[0],a[-1]+1) ? - steinerkelvin

@kelvinss 我在想他的数组始终从1开始，因为他问如果1、2、3丢失会怎么样。 - Saša Šijak

我意识到第二个参数中的 +1 并不重要。但我认为 range(1,a[-1]) 更清晰明了。 - steinerkelvin

1

我相信这是解决一般情况下最简洁的解决方案。其他提到的算法没有考虑空隙。例如: a=[1, 2, 4, 99]。你的方法适当地处理了这个问题。 - James

7

还有一种使用 itertools 模块的方法：

from itertools import count, izip

a=[1,2,3,4,5,7,8,9,10]
nums = (b for a, b in izip(a, count(a[0])) if a != b)
next(nums, None)
# 6

- Jon Clements

2

这将处理首尾数字缺失的情况。

>>> a=[1,2,3,4,5,7,8,9,10]
>>> n = len(a) + 1
>>> (n*(n+1)/2) - sum(a)
6

- JMortey

1

def find(arr):
        for x in range(0,len(arr) -1):
                if arr[x+1] - arr[x] != 1:
                        print arr[x] + 1

- Prat_yow

1

L=[-5,1,2,3,4,5,7,8,9,10,13,55]

missing=[]

for i in range(L[0],L[-1]):
    if i not in L:
        missing.append(i)
print(missing)

- Joe121

嗨，Joe，已经有17个其他答案了，如果您能添加一些解释来帮助我们理解它与其他答案的不同之处以及它是如何以其他答案无法解决的方式解决问题的，那就太好了。谢谢！ - Simas Joneliunas

1

def findAllMissingNumbers(a):
   b = sorted(a)
   return list(set(range(b[0], b[-1])) - set(b))

- Shyambeer Singh

1

如果列表中有许多缺失的数字：

>>> a=[1,2,3,4,5,7,8,10]
>>> [(e1+1) for e1,e2 in zip(a, a[1:]) if e2-e1 != 1]
[6, 9]

- ndpu

1

你可能想说 e2-e1 != 1。 - thefourtheye

如果 a=[1,2,3,4,5,8,10]，那会怎样？ - Abhijit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Abhijit · Accepted Answer

>>> a=[1,2,3,4,5,7,8,9,10]
>>> sum(xrange(a[0],a[-1]+1)) - sum(a)
6

另一种方法是使用等差数列求和公式

>>> a[-1]*(a[-1] + a[0]) / 2 - sum(a)
6

对于一般情况下可能丢失多个数字的情况，您可以制定O(n)方法。

>>> a=[1,2,3,4,7,8,10]
>>> from itertools import imap, chain
>>> from operator import sub
>>> print list(chain.from_iterable((a[i] + d for d in xrange(1, diff))
                        for i, diff in enumerate(imap(sub, a[1:], a))
                        if diff > 1))
[5, 6, 9]