Denke wie ein Programmierer: Problemlösung

Intro

Um meine Programmierkenntnisse auf dem neuesten Stand zu halten, löse ich von Zeit zu Zeit Aufgaben auf LeetCode. Es ist großartig, weil es sich ständig weiterentwickelt, eine freundliche Benutzeroberfläche hat, du Probleme zu Themen auswählen kannst, die dich interessieren, und es eine hervorragende Community gibt, von der du viel lernen kannst.

Ich habe mich schon immer dafür interessiert, was in den Köpfen der Programmierer/innen vorgeht, wenn sie Probleme lösen. Wie läuft das wirklich ab? Da ich kein Material zu diesem Thema finden konnte, beschloss ich, darüber zu schreiben, wie es mir passiert ist.

Diese Veröffentlichung im LeetCode-Community-Forum hat ziemlich viele Reaktionen hervorgerufen und Hunderte von Bewertungen erhalten, also teile ich meine Erfahrungen auch hier im Blog.

Aufgabe

Hier ist die Aufgabe selbst:

Sortiere ein Array mit ganzen Zahlen in aufsteigender Reihenfolge nach der Häufigkeit der Werte. Wenn mehrere Werte die gleiche Häufigkeit haben, sortiere sie in absteigender Reihenfolge. Gib das sortierte Array zurück.

Example 1:

Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Erklärung: “3” hat eine Häufigkeit von 1, “1” hat eine Häufigkeit von 2 und “2” hat eine Häufigkeit von 3.

Start

Früher Sonntagmorgen, Musik von Spotify, heißer Kaffee, Lieblingskonsole, gute Laune… Aufgabe von der Liste der “später zu lösenden” Aufgaben.

Los geht’s! Python starten, erste Eingaben machen…

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]

Denke

Ok, ich muss also die Häufigkeit der einzelnen Werte zählen… Erste Idee - verwende Counter. Dieser liefert ein Objekt vom Typ 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'>

Jetzt muss ich diese Werte gemäß den Anforderungen in der Beschreibung sortieren. Das Objekt Counter hat kein Attribut sort, und sorted sortiert nur Werte, nicht Häufigkeiten. Beim Googeln der Optionen fand ich diese StackOverflow-Frage mit vielen nützlichen Antworten. Lesen… Versuchen wir es mit einem einfacheren Objekt:

1

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

Dies gibt eine Liste von Tupeln zurück, wobei die erste Zahl der Wert und die zweite die Häufigkeit ist. Kann ich sie mit demselben Befehl sortieren? Springe zur offiziellen Dokumentation. Nein, im Befehl selbst kann nicht sortiert werden: “Elemente mit gleicher Anzahl werden in der Reihenfolge des ersten Auftretens sortiert”. Ok, lass uns direkt sortieren, zuerst nach Werten in absteigender Reihenfolge, dann nach Häufigkeiten in aufsteigender.

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

Sieht vielversprechend aus. Jetzt möchte ich diese Tupel zu einer einzigen Liste erweitern… Ich suche immer noch nach Antworten auf dieselbe Frage. Ich erinnere mich, dass ich das Tupel erweitern und jede Zahl daraus erhalten kann, indem ich dies verwende:

1
2
3
4
5

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

Dann kann ich jeden Wert um die Zahl seiner Häufigkeit wiederholen:

1
2

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

Aha. Jetzt brauche ich eine leere Liste, um all diese Tupel zu einer einzigen Liste zusammenzufassen:

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]

Juhu! Das ist genau das, was ich brauche. Die vollständige Lösung sieht jetzt so aus:

 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

Ergebnis: Ausführungszeit: 52 ms und ist damit schneller als 63,30 % der anderen Python 3-Lösungen für die Sortierung von Arrays in aufsteigender Reihenfolge.

Speichernutzung: 14,2 MB, weniger als 58,20% der anderen Python 3 Lösungen für aufsteigende Array-Sortierung.

Nicht die beste, aber die Aufgabe ist gelöst.

Optimieren

Jetzt ist es Zeit für einen weiteren Spaß - kann ich es zu einem Einzeiler machen oder die Lösung auf eine andere Weise optimieren?

Schau dir die Sortierzeilen an… Kann ich sie in einem Zug sortieren? Ja! Also sortieren wir zuerst nach den Werten in umgekehrter Reihenfolge (-x[0]) und dann nach ihren Häufigkeiten (x[1]) in direkter Reihenfolge.

1

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

Im Grunde ist es derselbe Vorgang wie oben, aber jetzt in einer Zeile kodiert. Ich liebe Python :) Die gleiche Logik gilt auch für die Tupel-Erweiterung und ermöglicht es, eine weitere Zeile zu sparen:

1
2
3

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

Und dann dachte ich: Wenn ich nach Wert und Häufigkeit sortieren kann, warum brauche ich dann eine Zwischenliste? Kann ich die ursprüngliche Liste auch so sortieren?! Schauen wir mal…

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]

Voila! Das fühlt sich sooo gut an. Aber x.sort macht es in-place und ich muss ein Objekt zurückgeben… Also muss ich es in sorted ändern:

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]

Perfekt. Die endgültige Variante wäre also:

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

Und es ist sogar noch schneller!

Laufzeit: 44ms, schneller als 95,07% der anderen Python 3 Lösungen für aufsteigende Arraysortierung.

Speichernutzung: 14,3 MB, weniger als 58,20 % der anderen Python 3-Lösungen für die aufsteigende Array-Sortierung.

Fazit

Das Lösen von Programmieraufgaben erfordert eine Kombination aus Wissen, Erfahrung und kreativen Problemlösungsfähigkeiten. Wenn du den Denkprozess und die Techniken erfahrener Programmierer/innen verstehst, kannst du deine Fähigkeit verbessern, komplexen Code zu entschlüsseln und Hindernisse zu erkennen und zu überwinden.

Mit Übung und Ausdauer kann jeder ein erfahrener Programmierer werden und sich in seinem Bereich auszeichnen. Denk daran, immer neugierig zu bleiben und weiter zu lernen, denn Technologie und Programmiersprachen entwickeln sich ständig weiter.

Aber das Wichtigste ist: Habt Spaß!

😎