Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Lexikographische Permutation

Finde die k-te Anordnung verschiedener Zeichen in lexikographischer Reihenfolge.

Das lernst du

  • Ganze Blöcke von Permutationen auf einmal überspringen
  • Einen Rang in eine Permutation umwandeln
  • Mit 0-basierten und 1-basierten Positionen arbeiten

Problem

Schreibe alle Anordnungen der Zeichen von s in lexikographischer Reihenfolge auf. Für "abc" lautet die Liste abc, acb, bac, bca, cab, cba. Gib den k-ten Eintrag zurück, gezählt ab 1. Bei 12 Zeichen (479.001.600 Anordnungen) ist es zu langsam, die ganze Liste zu erzeugen. Jeder Block von Anordnungen, die mit demselben Zeichen beginnen, hat aber (Länge − 1)! Einträge, du kannst also ein Zeichen nach dem anderen festlegen.

Implementiere lexicographic_permutation(s, k).

Eingabe

s: Verschiedene Zeichen in beliebiger Reihenfolge.

k: Die Position in der sortierten Liste, gezählt ab 1.

Ausgabe

Gib die k-te Anordnung als String zurück. Zeichen werden nach ihren Zeichencodes verglichen, Ziffern kommen also vor Großbuchstaben und diese vor Kleinbuchstaben.

Einschränkungen

1 ≤ s.length ≤ 12; alle Zeichen von s sind verschieden; 1 ≤ k ≤ s.length!

Beispiele

Beispiel 1
Eingabe:
s = "abc"
k = 4

Erwartete Ausgabe:
expected = "bca"
Eingabe:
std::string s = "abc";
long long k = 4;

Erwartete Ausgabe:
std::string expected = "bca";
Eingabe:
string s = "abc";
long k = 4;

Erwartete Ausgabe:
string expected = "bca";

Erläuterung

Die Liste lautet abc, acb, bac, bca, cab, cba, und die vierte Anordnung ist "bca".

Beispiel 2
Eingabe:
s = "312"
k = 1

Erwartete Ausgabe:
expected = "123"
Eingabe:
std::string s = "312";
long long k = 1;

Erwartete Ausgabe:
std::string expected = "123";
Eingabe:
string s = "312";
long k = 1;

Erwartete Ausgabe:
string expected = "123";

Erläuterung

Die erste Anordnung sind die Zeichen in sortierter Reihenfolge: "123".

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Sortiere zuerst die Zeichen.

Hinweis 2

Jede Wahl des ersten Zeichens deckt (Länge − 1)! Permutationen ab. Teilst du k − 1 durch diese Zahl, weißt du, welches Zeichen an erster Stelle steht.

Hinweis 3

Entferne das gewählte Zeichen, behalte den Divisionsrest und wiederhole das mit den übrigen Zeichen.

Erwartete Komplexität

Zeit O(n²), zusätzlicher Speicher O(n)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.