Я новичок в питоне.

Есть вопрос в Hackerrank.

Учитывая массив неверных чисел и диапазон целых чисел, как я могу определить самый длинный сегмент целых чисел в этом включающем диапазоне, который не содержит неверного числа?

Например, вам дан нижний предел l = 3 и верхний предел r = 48, Массив badNumbers = [37,7,22,15,49,60]. Сегменты без плохих номеров [3,6], [8,14], [16,21], [23,36] и [38,48]. Самый длинный отрезок — [23,36] и это 14 элементов в длину.

Проблема: Описание функции Завершите функцию goodStatement в редакторе ниже. Функция должна возвращать целое число, обозначающее длину самого длинного непрерывного диапазона натуральных чисел в диапазоне от l до r включительно, который не включает никаких неправильных чисел.

goodSegment имеет следующий параметр (ы): badNumbers[badNumbers[0],...badNumbers[n-1]]: массив целых чисел l: целое число, нижняя граница, включительно r: целое число, верхняя граница, включительно

Ограничения $ 1 le n le 10 ^ 5 $, $ 1 le badNumbers[i] le 10 ^ 9 $, badNumbers содержит отдельные элементы

def goodSegment(badNumbers, l, r):
    ranges = []
    subrange = []
    large=0
    for i in range(l,r+1):
        if badNumbers.count(i)==0:
            if len(subrange)==0:
                subrange.append(i)
            else:
                if i==r:
                    subrange.append(i)
                    ranges.append(subrange)
                    if len(range(subrange[0],subrange[1]+1))>large:
                        large=len(range(subrange[0],subrange[1]+1))
        else:
            if len(subrange)==1:
                subrange.append(i-1)
                ranges.append(subrange)
                if len(range(subrange[0],subrange[1]+1))>large:
                    large=len(range(subrange[0],subrange[1]+1))
                subrange=[]
            else:
                subrange=[]
    
    return large

badNumbers=[5,4,2,15]
l=1
r=10
    
result = goodSegment(badNumbers, l, r)
print(result)

Код работает нормально. Но это не выполняется за 10 секунд согласно тестовым случаям хакерского ранга. Как я могу оптимизировать это для более быстрого выполнения?

PEP 8

В Руководство по стилю кода Python перечисляет множество рекомендаций:

• переменные и функции должны быть snake_case
• после запятых должен стоять пробел
• бинарные операторы должны быть окружены пробелом (например, l == r вместо того l==r, и r + 1 вместо того r+1)

Некоторые имена функций / переменных могут быть продиктованы вам проблемой кодирования, но для всех остальных вы должны следовать соглашениям PEP 8.

Оптимизация

Диапазон петли

for i in range(l, r + 1):

Предполагая, что ваш диапазон составляет от 1 до $ 10 ^ 9 $, этот цикл займет более 10 секунд, если код внутри цикла занимает более 10 наносекунд на итерацию. Это многого требует для интерпретируемого языка. Вам было бы лучше, если бы этот цикл можно было удалить.

Подробнее об этом чуть позже.

Подсчет -vs- существование

if badNumbers.count(i)==0:

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

badNumbers содержит отдельные элементы

Потому что badNumbers содержит уникальные элементы, счет будет либо 0, либо 1. Более того, как только мы найдем первое совпадение, мы можем прекратить счет, даже если уникальность была гарантирована, поскольку мы проверяем счет против нуля. На самом деле вам нужно просто спросить, i в badNumbers. Вы пишете именно так, как мы это сказали:

if i in badNumbers:

Это все еще $ O (п) $ операция, но будет быстрее. Как упоминалось в другом ответе, поворот badNumbers в набор ускорит это в $ O (1) $ операция. Но давайте рассмотрим другой вариант.

Сокращение данных

Ваш пример badNumbers = [37, 7, 22, 15, 49, 60] с ограничениями l=3 и r=48 показывает большую неэффективность. В badNumbers содержит числа вне пределов. Снова и снова глядя на эти числа (например, в badNumbers.count(i) == 0 или i in badNumbers) потрачено зря время.

Мы можем отфильтровать «плохие» плохие числа, которые в конечном итоге просто тратят время.

badNumbers = [number for number in badNumbers if l <= number <= r]

Организация ваших данных

Вы перебираете свои номера кандидатов, а затем эффективно ищите, есть ли номер кандидата в списке неверных номеров. Если этот список был отсортирован, вы могли бы просто поддерживать индекс до следующего несопоставленного неправильного числа и увеличивать его каждый раз, когда совпадение было найдено.

Объединяя это с предыдущим шагом:

badNumbers = sorted(x for x in badNumbers if l <= x <= r)

Теперь в вашем примере badNumbers было бы [7, 15, 22, 37]

Сейчас же, it = iter(badNumbers) создаст итератор, который сможет перемещаться по списку по порядку, bad_number = next(it) может извлечь следующее неверное число из списка, и мы также избавились от этого надоедливого индекса, о котором я упоминал выше.

Но я бы очень хотел избавиться от этого первого цикла, поэтому давайте воспользуемся другим подходом.

Длина зазора и концевые стойки

[7, 15, 22, 37]

В этом массиве мы сразу видим, что есть 15-7-1 хорошие числа между первыми двумя плохими числами, 22-15-1 между следующей парой и 37-22-1 между последней парой. Это почти все, что нам нужно, чтобы получить максимально продолжительную серию хороших чисел!

Чего не хватает, так это хорошего числа, идущего в начале и в конце списка. Мы можем исправить это, добавив несколько «конечных постов», лишние плохие числа, выходящие за пределы хороших конечных точек диапазона:

badNumbers = [l - 1] + sorted(x for x in badNumbers if l <= x <= r) + [r + 1]

В пределах l=3 и r=48, это создает badNumbers = [2, 7, 15, 22, 37, 49].

Теперь каждую пару чисел можно использовать для определения длины серии хороших чисел.

попарно

Поскольку мы хотим брать числа попарно, имеет смысл обратиться к Python itertools библиотека для соответствующей функции. Он не встроен, но pairwise рецепт может быть установлен из more-itertools.

Возьмите числа в виде пар, вычислив количество хороших значений между парой плохих значений и запомните максимальное значение. «Минус 1» из внутреннего расчета можно отложить до конца, для эффективности, т.к. $ max {(x_i-1)} == max {(x_i)} — 1 $

from more_itertools import pairwise

def goodSegment(bad_numbers, l, r):
    bad_numbers = [l - 1] + sorted(x for x in bad_numbers if l <= x <= r) + [r + 1]
    gap_lengths = (b - a for a, b in pairwise(bad_numbers))
    return max(gap_lengths) - 1

badNumbers = [5, 4, 2, 15]
l = 1
r = 10
    
result = goodSegment(badNumbers, l, r)
print(result)

Если more-itertools недоступен, вы можете сделать что-то почти эквивалентное

def pairwise(numbers):
    return zip(numbers[:-1], numbers[1:])

Он может быть даже быстрее, хотя будет использовать в три раза больше памяти.

Это $ O (п * м) $ потому что badNumbers.count(i), n и m — длины badNumbers и диапазон слева направо. Вы можете уменьшить это до $ O (п + т) $ если вы добавляете badNumbers в набор и проверяете, i есть в комплекте.

В функции вы делаете много ненужных вещей. Вам нужно только отслеживать текущую сумму и наибольшее количество чисел, которые вы видели в строке, которых не было в badNumbers. Никаких списков использовать не нужно.

Кстати, в паре мест вы можете сделать свой текущий код более плоским, используя elif вместо использования else и вложенных блоков if / else. В частности if i==r: и if len(subrange)==1:. Их можно было изменить на elif, а затем внизу else блок может быть убран.