Найти самый длинный последовательный диапазон чисел в списке

Question

У меня есть следующий список чисел:

numbers = numbers = [  1, 3, 11,  12,  14,  15,  16, 3, 4, 6]

Я хотел бы получить начальный и конечный индексы самого длинного последовательного диапазона чисел.Под последовательным диапазоном я подразумеваю целочисленный диапазон числа без пропуска, то есть 1,2,3,4,5 ...

Вот как я это сделал:

def get_longest_consecutive_numbers(numbers):

    # 1. Split the numbers list into sublists of consecutive numbers
    split_list = []
    j = 0
    for i in range(1,len(numbers)-1):
        if numbers[i]+1 is not numbers[i+1]:
            split_list.append(numbers[j:i])
            j = i

    # 2. Find index of longest sublist (of consecutive numbers)
    longest_sublist_index = max((len(l), i) for i, l in enumerate(split_list))[1]

    # 3. Concatenate all sublists up to this index back together
    rest = split_list[:longest_sublist_index]
    concat_list = [j for i in rest for j in i]

    # 4. 
    # Start Index: Length of concatenated list
    # End Index: Start Index + Length of longest sublist in split_list

    start_index = len(concat_list)
    end_index = start_index + len(split_list[longest_sublist_index])

    return start_index, end_index

Если я применяю свою функцию к списку чисел:

 get_longest_consecutive_numbers(numbers)

, я получаю:

(3, 6)

, что правильно ... но ...

Мне было интересно, есть ли более прямой (лучший) способ сделать это?

Answer 1

Вы также можете использовать для этого рекурсию:

numbers = [1, 3, 11,  12,  14,  15,  16, 3, 4, 6]

def getMaxConsecutiveInd(index):
    if numbers[index] + 1 == numbers[index + 1]:
        # call the functions if values are cosecutive to check next value
        return getMaxConsecutiveInd(index + 1)
    # return last index for cosecutive numbers
    return index


max_length, start_index, end_index = 0,0,0

i = 0
while i < len(numbers) - 1:
    con_index = getMaxConsecutiveInd(i)
    # if available max_length is less than new_max_length(con_index - i)
    # then change start_index and end_index  
    if max_length < con_index - i:
        max_length = con_index - i
        start_index = i
        end_index = con_index
    # change value of i to latest con_index if i != con_index
    if i == con_index:
        i = i + 1
    else:
        i = con_index

print(start_index, end_index, max_length)
Output: (4,6,2)

numbers = [1, 2, 3, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17, 18, 3, 4, 6]
Output: (0,6,6)

Answer 2

Вы можете использовать numpy.diff, чтобы вычислить различия между последовательными элементами в вашем списке, а затем использовать itertools.groupby, чтобы собрать эти элементы с разностями, равными 1.

import numpy as np
from itertools import groupby
from operator import itemgetter

def get_longest_consecutive_numbers(numbers):
    idx = max(
        (
            list(map(itemgetter(0), g)) 
            for i, g in groupby(enumerate(np.diff(numbers)==1), itemgetter(1)) 
            if i
        ), 
        key=len
    )
    return (idx[0], idx[-1]+1)

print(get_longest_consecutive_numbers(numbers))
#(4,6)

Answer 3

Давайте немного повеселимся:

1. Создайте диапазон, в который включен список

2. Симметричная разница этого со списком

3. Рассчитать максимальное расстояние между двумя следующими числами (дает максимальную длину)

4. Получить индекс начальной и конечной точки

Вот код:

def longest_weird(numbers):
    delta = list(set(range(max(numbers))).symmetric_difference(numbers))
    start,end = 0,0
    maxi = 0
    for i,x in enumerate(delta[:-1]):
        aux = max(maxi,delta[i+1]-x)
        if aux != maxi:
            start,end = (x+1,delta[i+1]-1)
            maxi = aux
    return numbers.index(start),numbers.index(end)

Answer 4

numbers = [  1, 3, 11,  12,  14,  15,  16, 3, 4, 6]

def longest(numbers):
    max, count_ = 1, 1
    start_idx, end_idx = 0, 0
    for i in range(len(numbers)-1):
        # if difference between number and his follower is 1,they are in sequence
        if numbers[i+1]-numbers[i] ==1:
            count_ = count_+1
        else:
            if count_ > max :
                max = count_
                end_idx = i
                start_idx = i+1 - max
            # Reset counter
            count_ = 1
    return (start_idx,end_idx,max)


print (longest(numbers))

выход:

(4, 6, 3) #start_idx, end_idx, len

Answer 5

Как насчет использования подхода с двумя указателями:

• set start = 0, end = 0
• set bestLen = 1, bestStart = 0
• в то время как end
• если числа [конец] + 1 == числа [конец + 1], тогда увеличить конец;установить bestLen = max (bestLen, end-start) (также установить bestStart = start, если вы только что обновили bestLen)
• еще увеличить end;установить начало = конец

вернуть диапазон [bestStart ... bestStart + bestLen]

Вы получите O (n) времени и O (1) дополнительное место.