找到不在区间列表中的最小数字

Question

我必须找到不在区间列表中的最小数字。例如，我有一个列表：[(2, 6), (0, 3), (9, 10)]。我必须通过检查从 0 到 10 的所有数字来找到最小的数字，直到找到不在这些范围内的最小数字。因此，数字不能介于 2 和 6（包括两者）、0 和 3、9 和 10 之间。

我写了一个函数，但我无法得到正确的答案。我总是得到程序检查的所有第一个数字，但我只需要最后一个。而且我不明白为什么它不适用于 return。

intervals = [(2, 6), (0, 3), (9, 10)]
def smallest_number(intervals):
   i = 0
   while True:
      for first, second in intervals:
         if i in range(first, second + 1):
            i += 1
            print(i)

print(smallest_number(intervals))

我期望输出 7，但我得到一个 7 的循环或从 1 到 7 的数字，具体取决于我放置 print(i) 的位置。

Answer 1

这是一种方法：

from itertools import chain
intervals = [(2, 6), (0, 3), (9, 10)]

ranges = chain.from_iterable(range(i, j+1) for i, j in l)
min(set(range(10)).difference(ranges))
# 7

详情

第一步创建一个set from the ranges contained in the tuples using a generator comprehension and calling range with both elements from each tuple. The result is flattened using itertools.chain:

ranges = chain.from_iterable(range(i, j+1) for i, j in l)
print(list(ranges))
# {0, 1, 2, 3, 4, 5, 6, 9, 10}

现在我们只需要寻找这个集合与range最大n

的差异min

diff = set(range(10)).difference(ranges)
# {7, 8}

Answer 2

我这里没有 Python 可以检查，但你的函数似乎没有 return 任何东西，所以 print(smallest_number(intervals)) 打印 None.

def smallest_number(intervals):
   i = 0
   while True:
      for first, second in intervals:
      if i in range(first, second + 1):
          i += 1
      else:
          return i

现在 print(smallest_number(intervals)) 应该可以了。

Answer 3

您的代码将在无限循环结束之前打印所有是的数字，而不是那些不是的数字。试试这个：

def smallest_number(intervals):
    i = 0
    while True:
        for first, second in intervals:
            if i in range(first, second + 1):
                i += 1
                break # break from inner loop
        else:
            break # break from outer loop
    return i # return number

此外，虽然 if i in range(first, second + 1): 在 Python 3 中还可以（而且很快），但我宁愿建议使用 if first <= i <= second:

或更短，使用 next 和 any:

def smallest_number(intervals, max_ = 10):
    return next((i for i in range(max_ + 1)
                 if not any(first <= i <= second for first, second in intervals)),
                None) # None is default if none is found

Answer 4

我的解决方案是在没有最小数量的情况下提供保护。

checking = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
intervals = [(2, 6), (0, 3), (9, 10)]
min_number = None

unique = set()
for left, right in intervals:
    unique.update(range(left, right + 1))

subset = set(checking) - unique
if subset:
    min_number = min(subset)

print(min_number)

Answer 5

如果您想要一个允许的数字列表，而不仅仅是最小的数字，这可能是一个不错的选择。

import itertools


def flatten(list_of_sublists):
    return itertools.chain.from_iterable(list_of_sublists)


def excluded_numbers(intervals):
    excluded_ranges = [range(lower, upper + 1) for lower, upper in intervals]
    excluded_numbers = set(flatten(excluded_ranges))
    return excluded_numbers


def permitted_numbers(intervals):
    excluded = excluded_numbers(intervals)
    max_excluded = max(excluded)
    candidates = set(range(max_excluded + 2))
    return candidates - excluded


def smallest_number(intervals):
    return min(permitted_numbers(intervals))

Answer 6

按起点对间隔进行排序（如果起点相等，则为终点）。然后从第一个区间开始，不断扩大右边界，直到下一个区间的起点大于我们当前的覆盖终点。

Take (2,6),(0,3),(9,10)
Sorting: (0,3),(2,6),(9,10)
current coverage = [0,3]

因为 3 < 6 且 2<3，我们可以将我们的右点增加到 6 所以覆盖范围变成 [0,6] 但是 6 < 9，所以 7 是不在任何区间中的最小数字。您还需要检查第一个间隔的起点是否 > 0。在这种情况下，答案将为 0。

找到不在区间列表中的最小数字

Find the smallest number that is not in a list of intervals

python

intervals