Python список манипуляция: Учитывая список диапазонов номеров, возвращает список объединенных диапазонов

Question

я получил эту проблему во время телефонного интервью:

Предположим, что существует список диапазонов. Например, [[1-6], [10-19], [5-8]]. Напишите функцию, которая возвращает список комбинированных диапазонов , так что вход [[1-6], [10-19], [5-8]] возвращается к функции [[1,8], [10,19 ]] (только начальный и конечный номера). Обратите внимание: список ввода может содержать произвольное количество диапазонов .

Мое решение этой проблемы:

1. Объединить весь список диапазона в один список: [[1-6], [10-19], [5-8]] -> [1-6,10-19,5-8]

2. Выполнение сортировки по списку: list = Сортировка (список) -> [1,2,3,4,5,5,6,6, 7,8,10 ...]

3. Использовать list = set (list), чтобы избавиться от избыточных чисел

4. Итерация по списку и найти диапазон

Я знаю, что это решение, безусловно, то, что они ищут (вот почему я провалил интервью ужасно) как время сложности O (NlogN) (сортировка), n - количество различных чисел в диапазоне.

Можете ли вы, эксперт python, дать решение O (n), n как количество диапазонов в исходном списке?

Answer 1

Прежде всего, решение, упомянутое в вопросе, не O (nlgn), где n - количество сегментов. Это O (Xlg (X)), где X = length of the segment*num of segments, что ужасно медленно. Существует решение O (NlgN), где N - количество сегментов.

1. Сортировка сегментов по их начальной точке.
2. Проведите по отсортированному списку и проверьте, совпадает ли текущий сегмент с предыдущим. Если да, то при необходимости продлите предыдущий сегмент.

Пример кода:

inp = [[1,6], [10,19], [5,8]] 

inp = sorted(inp) 
segments = [] 

for i in inp: 
    if segments: 
     if segments[-1][1] >= i[0]: 
      segments[-1][1] = max(segments[-1][1], i[1]) 
      continue 
    segments.append(i) 

print segments # [[1, 8], [10, 19]] 

Answer 2

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

import heapq 

def merge(ranges): 
    heapq.heapify(ranges) 
    res = [] 

    while ranges: 
     start, end = heapq.heappop(ranges) 
     if ranges and ranges[0][0] <= end: 
      heapq.heapreplace(ranges, [start, max(end, ranges[0][1])]) 
     else: 
      res.append((start, end)) 

    return res 

ranges = [[1,6],[10,19],[5,8]] 
print(merge(ranges)) 

Выход:

[(1, 8), (10, 19)] 

Над имеет О (п войти п) временную сложность, где п является числом диапазоны.

Answer 3

В случае диапазона [х, у] и max_x, у менее вероятно, в течение нескольких миллионов вы можете сделать это

Идея заключается в том, что я использую техника хеширования, чтобы поместить их в отсортированный порядок, используя более низкий max_y.

Затем мы повторяем и сохраняем текущий «хороший» диапазон - переменные mn и mx.

Когда новый диапазон приходит, если он полностью находится за пределами «хорошего» диапазона, мы добавляем хороший диапазон и делаем новый диапазон хорошим диапазоном. В противном случае мы соответственно меняем соответствующий диапазон.

max_y = 1000000 
range_sort = [None]*max_y 

ranges = [[1,6],[10,19],[5,8]] 
for r in ranges: 
    if range_sort[r[0]] is not None and range_sort[r[0]]>=r[1]: 
     continue ## handling the case [1,5] [1,8] 
    range_sort[r[0]] = r[1] # in the list lower value is stored as index, higher as value 

mx = -1 
mn = 1000000000 
ans = [] 
for x,y in enumerate(range_sort): # The values are correct as explained in comment above 
    if y is None: 
     continue #To remove the null values 

    if x<mn: 
     mn = x # This will change the lower value of current range 

    if x>mx and mx>0: # If lower val x higher than current upper mx 
     ans.append([mn,mx]) # append current lower (mn) and upper(mx) 
     mn = x 
     mx = y # change the current upper and lower to the new one 

    if y>mx: 
     mx = y # This will change upper value of current range 

ans.append([mn,mx]) # This has to be outside as last range won't get appended 

print ans 

Выход: [[1,8], [10,19]]

Временная сложность О (MAX_y)