Python 3 - Найти пропущенные диапазоны кортежей - PullRequest
Новая
       40

Python 3 - Найти пропущенные диапазоны кортежей

0 голосов
/ 03 марта 2019

Допустим, у меня есть некоторый диапазон int, начинающийся с 0 и заканчивающийся на 48.

Как мне найти пропущенную инклюзивную последовательность по заданным массивам? 

Given: [(10, 12), (12, 37)] 
Output: [(0,10),(37,48)]


Given: [(9, 15)] 
Output: [(0,9),(15,48)]


Given: [(0, 15), (15, 17), (17, 19), (21,25)] 
Output: [(19,21),(25,48)]


Given: [(23, 35),(40,47)] 
Output: [(0,23),(35,40),(47,48)]

Ответы [ 3 ]

0 голосов
/ 03 марта 2019

Если вы просто перебираете список и отслеживаете начальные и конечные значения, это можно сделать довольно просто, следуя предположению, что список отсортирован.Вы просто добавляете кортеж к результату, если текущий кортеж [0] больше начального значения.В конце вы проверите, есть ли у вас оставшиеся значения (если start < stop).

def getMissing(l, start, stop):
    newList = []
    for tup in l:
        if tup[0] > start:
            newList.append((start, tup[0]))
        start = tup[1]
    # add any left over values
    if start < stop:
        newList.append((start, stop))
    return newList

getMissing([(2, 12), (15, 46)], 0, 48)
# result: [(0, 2), (12, 15), (46, 48)]
0 голосов
/ 03 марта 2019

Вот простой метод, который проходит через каждый кортеж и проверяет, больше ли первый элемент, чем последний наибольший элемент, который мы видели: 

def get_gaps(tuples,l,r):
    """Return list of tuples representing gaps between l and r not covered by ranges in tuples."""

    # make sure tuples are sorted on first element
    tuples.sort()
    a= []

    for tup in tuples:
        if tup[0] > l:
            a.append((l,tup[0]))
        # update left marker to last seen (largest) element
        l = tup[1]

    # check final element of final tuple
    if r > l:
        a.append((l,r))

    return a

Примечание: этот метод предполагает, что кортежи не перекрываются и могутне дает правильных результатов, например, ((10, 20),(13,16))

0 голосов
/ 03 марта 2019

Нам нужно только выполнить итерацию в диапазоне кортежей sorted , найти недостающие элементы между позицией i в списке и позицией i+1.

Первый ипоследние кортежи являются крайними случаями и должны рассматриваться отдельно, а также пустым входным регистром.Вот возможный алгоритм: 

def find_missing_ranges(tuples, start=0, end=48):
    # edge case: empty input
    if not tuples:
        return [(start, end)]
    ans = []
    # sort the input
    lst = sorted(tuples)
    # edge case: handle start of range
    if lst[0][0] != 0:
        ans.append((start, lst[0][0]))
    for i in range(len(lst) - 1):
        # normal case, find holes between tuples i and i+1
        if lst[i][1] != lst[i + 1][0]:
            ans.append((lst[i][1], lst[i + 1][0]))
    # edge case: handle end of range
    if lst[-1][1] != end:
        ans.append((lst[-1][1], end))
    return ans

Он работает, как и ожидалось, с примером ввода: 

find_missing_ranges([])
=> [(0, 48)]

find_missing_ranges([(0, 48)])
=> []

find_missing_ranges([(10, 12), (12, 37)])
=> [(0, 10), (37, 48)]

find_missing_ranges([(9, 15)])
=> [(0, 9), (15, 48)]

find_missing_ranges([(0, 15), (15, 17), (17, 19), (21, 25)])
=> [(19, 21), (25, 48)]

find_missing_ranges([(23, 35), (40, 47)])
=> [(0, 23), (35, 40), (47, 48)]
...