25

假设我们在一个连续整数序列中丢失了两项，并且丢失的元素位于第一个和最后一个元素之间。我确实编写了一个完成任务的代码。但是，如果可能的话，我想使用更少的循环来提高效率。任何帮助将不胜感激。另外，当我们必须找到更多丢失的项目（比如接近 n/4）而不是 2 时，情况又如何呢？我认为我的代码应该是高效的，因为我更早地脱离了循环？

def missing_elements(L,start,end,missing_num):
    complete_list = range(start,end+1)
    count = 0
    input_index = 0
    for item  in  complete_list:
        if item != L[input_index]:
            print item
            count += 1
        else :
            input_index += 1
        if count > missing_num:
            break



def main():
    L = [10,11,13,14,15,16,17,18,20]
    start = 10
    end = 20
    missing_elements(L,start,end,2)



if __name__ == "__main__":
    main()
4

17 回答 17

57

如果输入序列是sorted，您可以在此处使用集合。从输入列表中获取开始值和结束值：

def missing_elements(L):
    start, end = L[0], L[-1]
    return sorted(set(range(start, end + 1)).difference(L))

这假设 Python 3；对于 Python 2，用于xrange()避免先构建列表。

sorted()调用是可选的；没有它，将set()返回缺失值，有了它，您将获得一个排序列表。

演示：

>>> L = [10,11,13,14,15,16,17,18,20]
>>> missing_elements(L)
[12, 19]

另一种方法是检测后续数字之间的差距；使用较旧的itertools库滑动窗口配方：

from itertools import islice, chain

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result

def missing_elements(L):
    missing = chain.from_iterable(range(x + 1, y) for x, y in window(L) if (y - x) > 1)
    return list(missing)

这是一个纯粹的 O(n) 操作，如果您知道丢失项目的数量，您可以确保它只产生这些然后停止：

def missing_elements(L, count):
    missing = chain.from_iterable(range(x + 1, y) for x, y in window(L) if (y - x) > 1)
    return list(islice(missing, 0, count))

这也将处理更大的差距；如果您在 11 和 12 缺少 2 项，它仍然可以工作：

>>> missing_elements([10, 13, 14, 15], 2)
[11, 12]

上面的示例只需要迭代[10, 13]来解决这个问题。

于 2013-06-06T23:49:58.240 回答
12

假设 L 是一个没有重复的整数列表，您可以推断列表的 start 和 index 之间的部分是完全连续的当且仅当L[index] == L[start] + (index - start)且类似地 index 和 end 是完全连续的当且仅当L[index] == L[end] - (end - index)。这与递归地将列表分成两个相结合，给出了一个次线性的解决方案。

# python 3.3 and up, in older versions, replace "yield from" with yield loop

def missing_elements(L, start, end):
    if end - start <= 1: 
        if L[end] - L[start] > 1:
            yield from range(L[start] + 1, L[end])
        return

    index = start + (end - start) // 2

    # is the lower half consecutive?
    consecutive_low =  L[index] == L[start] + (index - start)
    if not consecutive_low:
        yield from missing_elements(L, start, index)

    # is the upper part consecutive?
    consecutive_high =  L[index] == L[end] - (end - index)
    if not consecutive_high:
        yield from missing_elements(L, index, end)

def main():
    L = [10,11,13,14,15,16,17,18,20]
    print(list(missing_elements(L,0,len(L)-1)))
    L = range(10, 21)
    print(list(missing_elements(L,0,len(L)-1)))

main()
于 2013-06-07T01:37:32.783 回答
3 
missingItems = [x for x in complete_list if not x in L]
于 2013-06-06T23:51:25.380 回答
2

使用collections.Counter：

from collections import Counter

dic = Counter([10, 11, 13, 14, 15, 16, 17, 18, 20])
print([i for i in range(10, 20) if dic[i] == 0])

输出：

[12, 19]
于 2013-06-06T23:57:02.407 回答
2 

 a=[1,2,3,7,5,11,20]
 b=[]
 def miss(a,b):
     for x in range (a[0],a[-1]):
        if x not in a:
            b.append(x)
     return b
 print (miss(a,b))

回答：[4, 6, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19]

适用于sorted, unsorted,duplicates也

于 2019-12-05T05:03:24.087 回答
1

使用scipy库：

import math
from scipy.optimize import fsolve

def mullist(a):
    mul = 1
    for i in a:
        mul = mul*i
    return mul

a = [1,2,3,4,5,6,9,10]
s = sum(a)
so = sum(range(1,11))
mulo = mullist(range(1,11))
mul = mullist(a)
over = mulo/mul
delta = so -s
# y = so - s -x
# xy = mulo/mul
def func(x):
    return (so -s -x)*x-over

print int(round(fsolve(func, 0))), int(round(delta - fsolve(func, 0)))

计时：

$ python -mtimeit -s "$(cat with_scipy.py)" 

7 8

100000000 loops, best of 3: 0.0181 usec per loop

其他选项是：

>>> from sets import Set
>>> a = Set(range(1,11))
>>> b = Set([1,2,3,4,5,6,9,10])
>>> a-b
Set([8, 7])

时间是：

Set([8, 7])
100000000 loops, best of 3: 0.0178 usec per loop
于 2013-06-07T19:06:34.070 回答
1 
arr = [1, 2, 5, 6, 10, 12]
diff = []

"""zip will return array of tuples (1, 2) (2, 5) (5, 6) (6, 10) (10, 12) """
for a, b in zip(arr , arr[1:]):
    if a + 1 != b:
        diff.extend(range(a+1, b))

print(diff)

[3、4、7、8、9、11]

如果列表已排序，我们可以查找任何间隙。然后在当前（+1）和下一个值（不包括）之间生成一个范围对象，并将其扩展到差异列表。

于 2019-08-07T00:36:16.307 回答
0 
>>> l = [10,11,13,14,15,16,17,18,20]
>>> [l[i]+1 for i, j in enumerate(l) if (l+[0])[i+1] - l[i] > 1]
[12, 19]
于 2013-06-07T00:09:57.277 回答
0

这是一个单行：

In [10]: l = [10,11,13,14,15,16,17,18,20]

In [11]: [i for i, (n1, n2) in enumerate(zip(l[:-1], l[1:])) if n1 + 1 != n2]
Out[11]: [1, 7]

我使用列表，切片以将副本偏移一个，并使用枚举来获取丢失项目的索引。

set对于长列表，这不是很好，因为它不是 O(log(n))，但我认为与对小输入使用 a 相比，它应该非常有效。izip来自 itertools 可能会使其更快。

于 2013-06-06T23:50:20.830 回答
0

我的看法是不使用循环和设置操作：

def find_missing(in_list):
    complete_set = set(range(in_list[0], in_list[-1] + 1))
    return complete_set - set(in_list)

def main():
    sample = [10, 11, 13, 14, 15, 16, 17, 18, 20]
    print find_missing(sample)

if __name__ == "__main__":
    main()

# => set([19, 12])
于 2013-06-06T23:54:38.757 回答
0

只需遍历列表并查找不连续的数字：

prev = L[0]
for this in L[1:]:
    if this > prev+1:
        for item in range(prev+1, this):    # this handles gaps of 1 or more
            print item
    prev = this
于 2013-06-06T23:58:36.603 回答
0

如果两个连续数字之间的差大于 ，我们发现了一个缺失值1：

>>> L = [10,11,13,14,15,16,17,18,20]
>>> [x + 1 for x, y in zip(L[:-1], L[1:]) if y - x > 1]
[12, 19]

注意：Python 3。在 Python 2 中使用itertools.izip.

改进的版本中连续缺少一个以上的值：

>>> import itertools as it
>>> L = [10,11,14,15,16,17,18,20] # 12, 13 and 19 missing
>>> [x + diff for x, y in zip(it.islice(L, None, len(L) - 1),
                              it.islice(L, 1, None)) 
     for diff in range(1, y - x) if diff]
[12, 13, 19]
于 2013-06-07T00:06:12.423 回答
0

我偶然发现了这种寻找另一种效率的方法——给定一个可能非常稀疏的唯一序列号列表，产生下一个可用的序列号，而无需在内存中创建整个序列号。（想想一个物品来来往往频繁的库存，但有些是长期存在的。）

def get_serial(string_ids, longtail=False):
  int_list = map(int, string_ids)
  int_list.sort()
  n = len(int_list)
  for i in range(0, n-1):
    nextserial = int_list[i]+1
    while nextserial < int_list[i+1]:
      yield nextserial
      nextserial+=1
  while longtail:
    nextserial+=1
    yield nextserial
[...]
def main():
  [...]
  serialgenerator = get_serial(list1, longtail=True)
  while somecondition:
    newserial = next(serialgenerator)

（输入是整数的字符串表示列表，yield 是整数，因此不是完全通用的代码。如果我们超出范围，longtail 会提供外推。）

还有一个类似问题的答案，它建议使用位数组来有效地处理大量整数。

我的某些代码版本使用了 itertools 中的函数，但我最终放弃了这种方法。

于 2020-01-21T18:51:15.007 回答
0

首先我们应该对列表进行排序，然后我们检查除最后​​一个之外的每个元素，如果下一个值在列表中。注意不要在列表中有重复项！

l.sort()

[l[i]+1 for i in range(len(l)-1) if l[i]+1 not in l]
于 2017-08-30T11:39:17.837 回答
0

一点数学，我们得到一个简单的解决方案。以下解决方案适用于从 m 到 n 的整数。适用于已排序和未排序的正数和负数。

#numbers = [-1,-2,0,1,2,3,5]
numbers = [-2,0,1,2,5,-1,3]

sum_of_nums =  0
max = numbers[0]
min = numbers[0]
for i in numbers:
    if i > max:
        max = i
    if i < min:
        min = i
    sum_of_nums += i

# Total : sum of numbers from m to n    
total = ((max - min + 1) * (max + min)) / 2

# Subtract total with sum of numbers which will give the missing value
print total - sum_of_nums
于 2021-09-29T07:51:33.493 回答
0 
def missing_elements(inlist):
    if len(inlist) <= 1:
        return []
    else:
        if inlist[1]-inlist[0] > 1:
            return [inlist[0]+1] + missing_elements([inlist[0]+1] + inlist[1:])
        else:
            return missing_elements(inlist[1:])
于 2016-03-16T10:35:00.307 回答
-1

使用此代码，您可以找到序列中的任何缺失值，除了最后一个数字。它只需要将您的数据输入到列名为“数字”的excel文件中。

import pandas as pd
import numpy as np

data = pd.read_excel("numbers.xlsx")

data_sort=data.sort_values('numbers',ascending=True)
index=list(range(len(data_sort)))
data_sort['index']=index
data_sort['index']=data_sort['index']+1
missing=[]

for i in range (len(data_sort)-1):
    if data_sort['numbers'].iloc[i+1]-data_sort['numbers'].iloc[i]>1:
        gap=data_sort['numbers'].iloc[i+1]-data_sort['numbers'].iloc[i]
        numerator=1
        for j in range (1,gap):          
            mis_value=data_sort['numbers'].iloc[i+1]-numerator
            missing.append(mis_value)
            numerator=numerator+1
print(np.sort(missing))
于 2019-08-19T02:18:44.903 回答