Мой код «почтиIncreasingSequence (последовательность)» слишком медленный для списков, содержащих более 10000 элементов. [CodeSignal]

Я спросил это вопрос и о Stackoverflow, но я думаю, что он лучше всего подходит здесь, потому что мой код нуждается в оптимизации вместо проверки ошибок (как я раньше думал).

Я тоже внес изменения в свой код. Но логика почти такая же:

  • Мой код сначала проверяет длину предоставленной последовательности, если она равна 2 или меньше, он автоматически возвращает True.
  • Затем он создает newlist с удалением первого элемента и проверяет, находится ли остальная часть списка в порядке возрастания.
  • Если последовательность не в порядке, итерация breaks и newlist генерируется снова, на этот раз с удалением следующего элемента.
  • Это продолжается до тех пор, пока не останется элементов для удаления (т.е. i == len(sequence) - 1), который в конечном итоге возвращается как False
  • Если в любой из итераций список находится в порядке возрастания (т. Е. in_order останки True) функция возвращает True.
def almostIncreasingSequence(sequence):
    # return True for lists with 2 or less elements.
    if len(sequence) <= 2:
        return True

    # Outerloop, removes i-th element from sequence at each iteration
    for i in range(len(sequence)):
        newlist = sequence[:i] + sequence[i+1:]

        # Innerloop, checks if the sequence is in ascending order
        j = 0
        in_order = True
        while j < len(newlist) - 1:
            if newlist[j+1] <= newlist[j]:
                in_order = False
                break
            j += 1
        if in_order == True:
            return True
        elif i == len(sequence)-1:
            return False
 
        

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

  1. Мне нужно удалить каждый следующий элемент из исходной последовательности. (внешний цикл)
  2. Мне нужно проверить, все ли элементы в порядке. (внутренний цикл)

Этот краткое описание almostIncreasingSequence() мой код следует логике, приведенной в ответе здесь, он также решает почти все тесты, но он слишком медленный для больших списков (которые содержат около 10000+ элементов).

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *