すべてのチャレンジ
中級 0件解決済み 正答率0%

辞書順で k 番目の順列

互いに異なる文字の並べ方のうち、辞書順で k 番目のものを求めます。

このチャレンジで学べること

  • 順列のまとまりを一度に読み飛ばせる
  • 順位から順列を復元できる
  • 0 始まりと 1 始まりの位置を使い分けられる

問題

原文(英語)を表示

s の文字の並べ方をすべて辞書順に並べます。"abc" なら abc, acb, bac, bca, cab, cba です。その k 番目(1 から数えます)を返してください。12文字だと並べ方は 479,001,600 通りあり、すべて列挙していては間に合いません。同じ文字で始まる並べ方のまとまりには、それぞれ (長さ − 1)! 個が含まれるので、1文字ずつ決めていくことができます。

lexicographic_permutation(s, k) を実装してください。

入力

s:互いに異なる文字(順不同)。

k:並べたリストでの位置(1 から数えます)。

出力

k 番目の並べ方を文字列で返してください。文字は文字コードで比較するので、数字は大文字より前に、大文字は小文字より前に来ます。

制約

1 ≤ s.length ≤ 12; s の文字はすべて異なる; 1 ≤ k ≤ s.length!

例

例 1
入力:
s = "abc"
k = 4

期待される出力:
expected = "bca"
入力:
std::string s = "abc";
long long k = 4;

期待される出力:
std::string expected = "bca";
入力:
string s = "abc";
long k = 4;

期待される出力:
string expected = "bca";

解説

一覧は abc, acb, bac, bca, cab, cba で、4番目は "bca" です。

例 2
入力:
s = "312"
k = 1

期待される出力:
expected = "123"
入力:
std::string s = "312";
long long k = 1;

期待される出力:
std::string expected = "123";
入力:
string s = "312";
long k = 1;

期待される出力:
string expected = "123";

解説

最初の並べ方は、文字を昇順に並べたものなので "123" です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

まず文字を並べ替えておきます。

ヒント 2

先頭の文字を1つ選ぶごとに (長さ − 1)! 個の順列が含まれるので、k − 1 をその数で割れば先頭の文字が決まります。

ヒント 3

選んだ文字を取り除き、余りを使って残りの文字で同じことを繰り返します。

目安の計算量

時間 O(n²)、追加メモリ O(n)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。