Думай как программист: решение задачи

Введение

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

Мне всегда было интересно узнать, что происходит в голове у программистов, когда они решают задачи. Как это происходит на самом деле? Поскольку я не смог найти подходящего материала на эту тему, я решил сам написать о том, как это происходило у меня.

Эта публикация на форуме сообщества LeetCode вызвала довольно бурную реакцию и получила сотни голосов “за”, поэтому я делюсь этим опытом и здесь, в блоге.

Задача

Вот сама задача:

Учитывая массив целых чисел nums, отсортируй массив в возрастающем порядке, основываясь на частоте значений. Если несколько значений имеют одинаковую частоту, отсортируй их в порядке убывания. Верни отсортированный массив.

Пример 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Объяснение: “3” имеет частоту 1, “1” имеет частоту 2, а “2” имеет частоту 3.

Начало

Раннее воскресное утро, музыка из Spotify, горячий кофе, любимая командная строка, отличное настроение… Задание из списка задач “Решить Позже”.

Начинаем! Запускаю Python, ввожу начальные значения…

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]

Думаем

Итак, мне нужно подсчитать частоту встречаемости каждого из уникальных значений… Первая идея - использовать Counter. Это возвращает тип объекта 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'>

Теперь мне нужно отсортировать эти значения, следуя требованиям в описании. У объекта Counter нет атрибута sort, а sorted будет сортировать только значения, а не частоты. Погуглив различные варианты, нашел вот этот вопрос на StackOverflow со множеством полезных ответов. Читаем… Пробуем более простой объект:

1

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

Это возвращает список кортежей, где первое число - значение, а второе - его частота. Могу ли я отсортировать его в этой же команде? Идем и читаем официальную документацию. Неа, не сортируется в самой команде, более того: “Элементы с одинаковым количеством упорядочиваются в порядке первой встречи”. Хорошо, давай отсортируем напрямую, сначала по значениям в порядке убывания, затем по частотам в порядке возрастания.

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)]

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

1
2
3
4
5

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

тогда я смогу повторять каждое значение по числу его частоты вот так:

1
2

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

Ага. Теперь мне нужен пустой список, чтобы объединить все эти кортежи в один список:

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]

Вууу-хууу! Это то, что мне нужно. Так что полное решение теперь выглядит следующим образом:

 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

Результат: Время выполнения: 52 мс, быстрее, чем 63,30% других решений на Python 3 для сортировки массива по возрастающей частоте.

Использование памяти: 14,2 МБ, меньше, чем у 58,20% других решений на Python 3 для сортировки массива по возрастающей частоте.

Не самый лучший вариант, но задача решена.

Улучшаем

Теперь пришло время для очередной забавы - смогу ли я сделать решение в одну строку или оптимизировать решение каким-либо другим способом? Это уже просто баловство + тренировка + удовольствие :)

Смотрим на сортировку строк… Могу ли я отсортировать их за один раз? Да! Итак, сначала мы сортируем по значениям в обратном порядке (-x[0]), а затем по их частотам (x[1]) в прямом порядке.

1

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

По сути, это та же операция, что и выше, но теперь закодированная в одну строку. Люблю Python :) Та же логика применима к части расширения кортежа, и это позволяет нам сэкономить еще одну строку:

1
2
3

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

И тут я подумал - если я могу сортировать по значению и его частоте, зачем мне нужен промежуточный список? Могу ли я отсортировать исходный список тем же способом?! Давай посмотрим…

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]

Вуаля! Это так здорово. Но x.sort делает это in-place, т.е. прямо в самом исходном объекте, а мне нужно вернуть новый объект… Поэтому мне нужно изменить операцию на 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]

Идеально. Поэтому окончательный вариант будет таким:

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))

И это еще быстрее!

Время выполнения: 44 мс, быстрее, чем 95,07% других решений на Python 3 для сортировки массива по возрастающей частоте.

Использование памяти: 14,3 МБ, меньше, чем у 58,20% других решений на Python 3 для сортировки массива по возрастающей частоте.

Заключение

Решение задач по программированию требует сочетания знаний, опыта и творческих навыков решения проблем. Понимая ход мыслей и приемы, используемые опытными программистами, ты сможешь улучшить свою способность разбивать сложный код на части, выявлять и преодолевать препятствия.

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

Но самое главное - получай удовольствие!

😎