Feda /dev/ - No Javascript allowed

#45481 dijo el de las culturales

#45468 pero da tu solución hombre.

#45488 ¿Le ves trabajar en Uber?

#45485 Se puede hacer en O(n), con un sólo recorrido, sin reordenar nada y sin hacer copias de todo el array, aunque el código resultante es #feo.

Partes en la cabeza de un rango [1, size+1] porque el caso peor sería {1, 2, 3... size} y en ese caso el resultado sería size+1.

Por ejemplo si te dan:

{4, -3, 2, 8, -1, 6, 3, 1, 7} (size = 9)

empiezas con [1, 10] porque el peor caso posible con tamaño 9 sería {1, 2, 3, 4, 5, 6, 7, 8, 9} y el resultado sería 10 así que nunca va a poder ser > 10. Este concepto puedes llevarlo simplemente con una pareja de ints: un 1 y un 10.

En cada iteración en la que te encuentres un número dentro de tu rango abres un hueco.

    [1, 10]
 4: [1, 3] ∪ [5, 10]
-3: [1, 3] ∪ [5, 10]
 2: [1, 1] ∪ [3, 3] ∪ [5, 10] = 1 ∪ 3 ∪ [5, 10]
 8: 1 ∪ 3 ∪ [5, 7] ∪ [9, 10]  = 1 ∪ 3 ∪ [5, 7] ∪ 9 ∪ 10
-1: 1 ∪ 3 ∪ [5, 7] ∪ 9 ∪ 10
 6: 1 ∪ 3 ∪ [5, 5] ∪ [7, 7] ∪ 9 ∪ 10 = 1 ∪ 3 ∪ 5 ∪ 7 ∪ 9 ∪ 10
 3: 1 ∪ 5 ∪ 7 ∪ 9 ∪ 10
 1: 5 ∪ 7 ∪ 9 ∪ 10
 7: 5 ∪ 9 ∪ 10

Devuelves tu primer valor del rango, en este caso 5. Si te pasan un array vacío el rango [1, size+1] es [1, 1] y 1 es el resultado correcto así que por ahí estás cubierto.

Conceptualmente se me ocurre esto pero quizás haya algo más simple. Además traducirlo a código debe de ser horrible por tener que andar bailando con esas parejas de ints.

¿Alguien sabe una forma mejor?

#45498 Esas chorradas nunca funcionan porque el más común de los mortales tarda un rato en dormirse, más aún si es en horas raras. Como te descuadres un poco ya la has cagado.

#45498 es interesante. Algún que otro día que me ha tocado dormir 5-6 horas, con siestas de 20-30 mins cada X horas me he sentido más activo y con más energía que durmiendo 7-9h del tirón. Más de una vez me he planteado dormir solo 6h y echarme 1 siesta de 30mins luego de comer que es cuando más sueño tengo para aprovechar mejor el día .