El objetivo del código es ver si una secuencia está casi aumentando, es decir, se puede aumentar estrictamente eliminando un solo elemento.

Por ejemplo: [1, 3, 2, 3] aumentaría estrictamente si se eliminara el elemento en el índice 1. [1, 2, 1, 2] no está casi aumentando porque si elimina el primer '2', obtendría [1, 1, 2] que no está aumentando estrictamente.

Mi código tiene que funcionar en menos de 4000 ms para una secuencia de longitud 2 <= len <= 10 ^ 5. Es probable que quede atrapado en secuencias muy largas.

def almostIncreasingSequence(sequence):
    length = len(sequence)
    count = 0

    for previous, next in zip(sequence[:-1],sequence[1:]):
        if previous < next:
            count +=1

    if (length-count>2):
        return False
    return True

[1, 2, 1, 2]

[1, 2, 3, 4, 5, 3, 5, 6]

[40, 50, 60, 10, 20, 30]

No funcionaría ... alguna ayuda por favor

Tenga en cuenta que esta no es una pregunta de tarea, como la mayoría de ustedes saben, hay muchas respuestas a esta pregunta publicadas en línea y me preguntaba si puedo hacerlo de esta manera

0
David L 9 oct. 2019 a las 04:20

3 respuestas

La mejor respuesta

Esto funciona:

import timeit
import random


def increasing_sequence_pos(sequence):
    for n, (a, b) in enumerate(zip(sequence[:-1], sequence[1:])):
        if a >= b:
            return False, n + 1
    return True, -1


def almost_increasing_sequence(sequence):
    increasing, n = increasing_sequence_pos(sequence)
    return (
        # either it was already increasing
        increasing or
        # or the problem is with the last element
        n == len(sequence)-1 or
        ((
            # or the element at position n was the problem
            (sequence[n - 1] < sequence[n + 1]) or
            # or the element at position n-1 was the problem
            (sequence[n - 2] < sequence[n] < sequence[n + 1])
        ) and increasing_sequence_pos(sequence[n + 1:])[0])
    )


size = 1000000

# time on simple increasing series
numbers = list(range(size))
print(timeit.timeit(lambda: almost_increasing_sequence(numbers), number=1))
print(f'Result: {almost_increasing_sequence(numbers)}')

# time on single issue
numbers[random.randint(1, size)] = 0
print(timeit.timeit(lambda: almost_increasing_sequence(numbers), number=1))
print(f'Result: {almost_increasing_sequence(numbers)}')

# time on two issues issue
numbers[random.randint(1, size)] = 0
print(timeit.timeit(lambda: almost_increasing_sequence(numbers), number=1))
print(f'Result: {almost_increasing_sequence(numbers)}')

Observe cómo obtiene tiempos variables y, por supuesto, el tiempo depende del hardware en el que está ejecutando, por lo que "4000ms" es bastante tonto (y muy fácil de lograr en computadoras modernas, incluso con un código muy, muy malo).

Notarás que el primero es bastante estable (0.07 segundos en mi estación de trabajo), mientras que el segundo y el tercero suelen tardar mucho más o menos.

Ejemplo de salida:

0.07000060000000001
Result: True
0.06909959999999998
Result: True
0.06430069999999999
Result: False

Tenga en cuenta que una secuencia creciente también se considera una secuencia casi creciente.

0
Grismar 11 oct. 2019 a las 02:10

Tu algoritmo ni siquiera es correcto. Solo está comprobando si hay uno o menos elementos que es más pequeño que el anterior. Sin embargo, no significa que sea una secuencia "casi creciente".

En resumen, cuando se encuentra con un elemento que es más pequeño que su anterior, la secuencia es "casi creciente" si la secuencia es "estrictamente creciente" al eliminar ese elemento en sí, O al eliminar el elemento anterior.

E.g.

1, 2, 3, [2*], 4, 5, 6
1, 2, 3, 100*, [4], 5, 6
1, 2, 3, [1], 2, 3

En el primer ejemplo 2, el número en [] es el elemento que es más pequeño que el anterior. Sin embargo, el número con * es el número que debe eliminarse para formar una secuencia estrictamente creciente. El tercer ejemplo es un ejemplo que contiene solo 1 elemento que es más pequeño que el anterior, pero no es una secuencia casi creciente

Entonces, la lógica más directa (en pseudocódigo) es algo así como:

def is_almost_increasing(seq):
    for i in 1 to len(seq):
        if seq[i] <= seq[i-1]:
            return (  is_strictly_increasing(seq[:i-1] + seq[i:] 
                     or is_strictly_increasing(seq[:i] + seq[i+1:] )
    return true

(is_strictly_increasing is simple, will just leave it to you)

Hay algunos trucos para hacerlo aún más rápido (por ejemplo, no es necesario volver a verificar la parte que ya ha confirmado que está aumentando), pero este debería ser un buen punto de partida para usted.

0
Adrian Shum 10 oct. 2019 a las 02:06
def seqIncCheck(lst):
    temp = lst[0]
    for i in range(1,len(lst)):
        if lst[i] > temp:
           temp = lst[i]
           continue
        else:
           return False
    return True
0
Z. Cajurao 9 oct. 2019 a las 02:41
58295858