Piensa como un programador: Resolución de problemas

Intro

Para mantener afilados mis conocimientos de programación, de vez en cuando resuelvo problemas en LeetCode. Es genial porque está en constante evolución, tiene una interfaz amigable, puedes elegir problemas sobre temas que te interesen y hay una comunidad excelente, de la que puedes aprender mucho.

Siempre me ha interesado saber qué pasa por la cabeza de los programadores cuando resuelven problemas. ¿Cómo ocurre realmente? Como no pude encontrar ningún material sobre el tema, decidí escribir sobre cómo me ocurrió a mí.

Esta publicación en el foro de la comunidad LeetCode provocó bastante respuesta y obtuvo cientos de upvotes, así que comparto mi experiencia también aquí en el blog.

Tarea

Ésta es la tarea

Dada una matriz de números enteros, ordena la matriz en orden creciente según la frecuencia de los valores. Si varios valores tienen la misma frecuencia, ordénalos en orden decreciente. Devuelve la matriz ordenada.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explicación: “3” tiene una frecuencia de 1, “1” tiene una frecuencia de 2, y “2” tiene una frecuencia de 3.

Comienza

Domingo por la mañana temprano, música de Spotify, café caliente, consola favorita, buen humor… Tarea de la lista de tareas “para resolver más tarde”.

¡Ahí está! Iniciar Python, introducir la entrada inicial…

1
2
3
4
5

~ ❯ python3                                                                         
Python 3.9.1 (default, Feb 3 2021, 07:38:02)
[Clang 12.0.0 (clang-1200.0.32.29)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> nums = [1,1,2,2,2,6,6,4,4,5,5,3]

Piensa en

Vale, necesito contar la frecuencia de cada uno de los valores únicos… Primera idea: utilizar Contador. Éste devuelve un objeto de tipo collection:

1
2
3
4
5

>>> d = Counter(nums)
>>> d
Counter({2: 3, 1: 2, 6: 2, 4: 2, 5: 2, 3: 1})
>>> type(d)
<class 'collections.Counter'>

Ahora necesito ordenar esos valores siguiendo los requisitos de la descripción. El objeto Counter no tiene el atributo sort, y sorted sólo ordenará valores, no frecuencias. Buscando opciones en Google, encontré esta pregunta de StackOverflow con muchas respuestas útiles. Leyendo… Probemos con un objeto más sencillo:

1

>>> r = Counter(nums).most_common()

Esto devuelve una lista de tuplas, donde el primer número es el valor y el segundo - su’ frecuencia. ¿Puedo ordenarlo en el mismo comando? Saltando a la documentación oficial. No, no se puede ordenar en el propio comando, además “Los elementos con recuentos iguales se ordenan en el orden en que se encuentran primero”. Vale, ordenémoslo directamente, primero por valores en el orden decreciente, luego por frecuencias en el creciente.

1
2
3
4

>>> r.sort(key = lambda x: x[0], reverse=True)
>>> r.sort(key = lambda x: x[1])
>>> r
[(3, 1), (6, 2), (5, 2), (4, 2), (1, 2), (2, 3)]

Parece prometedor. Ahora quiero expandir esas tuplas en una sola lista… Sigo buscando respuestas a la misma pregunta. Recordando que puedo expandir la tupla y obtener cada número de ella utilizando esto

1
2
3
4
5

>>> a, b = (3, 2)
>>> a
3
>>> b
2

para que luego pueda repetir cada valor por el número de su frecuencia, así:

1
2

>>> [3]*2
[3, 3]

Eso. Ahora necesito una lista vacía para combinar todas esas tuplas en una sola lista:

1
2
3
4
5
6
7

t = []
for i in r:
    a, b = i
    t.extend([a] * b)

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

¡Woo-hoo! Eso es lo que necesito. Así que la solución completa tiene ahora este aspecto:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        
        r = Counter(nums).most_common()
        r.sort(key = lambda x: x[0], reverse=True)
        r.sort(key = lambda x: x[1])
        
        t = []
        for i in r:
            a, b = i
            t.extend([a]*b)
            
        return t

Resultado: Tiempo de ejecución: 52 ms, más rápido que el 63,30% de otras soluciones de Python 3 para la ordenación de matrices en frecuencia ascendente.

Uso de memoria: 14,2 MB, menos que el 58,20% de otras soluciones de Python 3 para la ordenación ascendente de matrices.

No es lo mejor, pero la tarea está resuelta.

Optimizar

Ahora es el momento de otra diversión: ¿puedo hacer que sea de una sola línea u optimizar la solución de alguna otra forma?

Mirando las líneas de ordenación… ¿Puedo ordenarlo de una sola vez? ¡Sí! Así que primero ordenamos por valores en orden inverso (-x[0]) y luego por sus frecuencias (x[1]) en orden directo.

1

>>> r.sort(key = lambda x: (x[1], -x[0]))

Básicamente, es la misma operación que la anterior, pero ahora codificada en una sola línea. Me encanta Python :) La misma lógica se aplica a la parte de expansión de la tupla y permite ahorrar otra línea:

1
2
3

t = []
for i in r:
  t += ([i[0]] * i[1])

Y entonces pensé: si puedo ordenar por valor y su frecuencia, ¿para qué necesito una lista intermedia? ¿Puedo ordenar la lista original de la misma manera? Veamos…

1
2
3
4
5
6
7
8

>>> nums
[1, 1, 2, 2, 2, 6, 6, 4, 4, 5, 5, 3]
>>> r = Counter(nums)
>>> r
Counter({2: 3, 1: 2, 6: 2, 4: 2, 5: 2, 3: 1})
>>> nums.sort(key=lambda x: (r[x], -x))
>>> nums
[3, 6, 6, 5, 5, 4, 4, 1, 1, 2, 2, 2]

¡Voilà! Me siento taaaan bien. Pero x.sort lo hace in-place y necesito devolver un objeto… Así que tengo que cambiarlo por sorted:

1
2
3

>>> result = sorted(nums, key=lambda x: (r[x], -x))
>>> result
[3, 6, 6, 5, 5, 4, 4, 1, 1, 2, 2, 2]

Perfecto. Así que la variante final sería

1
2
3
4

class Solution:
    def frequencySort(self, nums: List[int]) -> List[int]:
        r = Counter(nums)
        return sorted(nums, key=lambda x: (r[x], -x))

¡Y es aún más rápido!

Tiempo de ejecución: 44 ms, más rápido que el 95,07% de las demás soluciones de Python 3 para la ordenación ascendente de matrices.

Uso de memoria: 14,3 MB, inferior al 58,20% de otras soluciones de Python 3 para la ordenación ascendente de matrices.

Conclusión

Resolver tareas de programación requiere una combinación de conocimientos, experiencia y habilidades creativas para resolver problemas. Si comprendes el proceso de pensamiento y las técnicas que utilizan los programadores experimentados, podrás mejorar tu capacidad para descomponer código complejo e identificar y superar obstáculos.

Con práctica y perseverancia, cualquiera puede convertirse en un programador competente y destacar en su campo. Recuerda mantener siempre la curiosidad y seguir aprendiendo, ya que la tecnología y los lenguajes de programación evolucionan continuamente.

Pero lo más importante, ¡diviértete!

😎