Блог

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

 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)
  

что правильно … но…

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

 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
  

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

 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)


  

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

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)
  

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

• установить start=0, end=0
• установите bestLen=1, bestStart=0
• в то время как end < len(числа) — 1
  • если числа [end] 1 == числа [end 1], то увеличьте end; установите bestLen = max(bestLen, end-start) (также установите bestStart = start, если вы только что обновили bestLen)
  • else увеличить end; установить start = end
• возвращает диапазон [bestStart … bestStart bestLen]

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

Вы можете использовать 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)