[解決済み] [解答】ある数字が与えられたとき、元の数字と全く同じ桁数の次の数字を求めよ。

質問

面接に失敗して、面接の質問もほとんど進まなかったんです。どうすればいいのか、どなたか教えてください。ネットで検索してみましたが、見つかりませんでした。

ある数字が与えられたとき、全く同じ数字を持つ次の数字を求めます。 元の数字と同じ数字の集合です。例：38276が与えられた場合 38627

私は、まず（右から）1桁目の数字が1より小さいインデックスを探したいと思いました。それから、その部分集合の最後の桁を回転させて、同じ桁で構成される次の最大の数になるようにしたかったのですが、行き詰まりました。

面接官も1桁ずつ入れ替えてみることを勧めてくれたのですが、アルゴリズムがわからず、20～30分くらい画面とにらめっこしていましたね。言うまでもなく、就職活動は続けなければならないと思っている。

edit: 参考までに、次の面接に招待されました。

解決方法は？

で行うことができます。 O(n) (ここで n は桁数)のようなものです。

右から順に、左の桁が右の桁より小さくなるような最初の2桁の組を見つけます。 左の数字を "digit-x"と呼ぶことにします。 digit-xの右側で、digit-xより大きい最小の数を求め、それをdigit-xのすぐ左に置きます。 最後に、残りの数字を昇順に並べ替えます。 降順 を逆順にすればよいのです。 (で正しい位置に配置できるdigit-xを除きます）。 O(n) ) .

例を挙げると、より分かりやすくなります。

123456784987654321
数字から始める

123456784 987654321
         左の数字が右より小さい右から1番目の場所  
         桁の "x" は 4 です。

123456784 987654321
              ^右側の4より大きい最小の桁を探す

123456785 4 98764321
        4の左側に置く

123456785 4 12346789
123456785123446789
         ^5の右側にある数字を並べ替える。 を除くすべての数字が 
         4」はすでに降順になっているので、あとは 
         順番を逆にして、'4'の正しい位置を見つける。

正しさを証明する。

桁の文字列を大文字で定義し、数字を小文字で定義することにしましょう。構文 AB というのは 文字列を連結したものです。 A と B "です。 . < は辞書順で、桁の文字列が同じ長さであれば整数順と同じです。

元の数Nは次のような形式です。 AxB ここで x は1桁の数字であり B は降順にソートされます。

このアルゴリズムで見つかった数値は AyC ここで y ∈ B は最小の数字 > x (の方法によって存在する必要があります）。 x が選択された、上記参照) および C は昇順にソートされます。

ある数字があると仮定する（同じ数字を使用する） N' そのような AxB < N' < AyC . N' で始まる必要があります。 A という形で書かないと間に入りませんので AzD . 今、私たちの不等式は AxB < AzD < AyC と等価である。 xB < zD < yC ここで、3つの数字列はすべて同じ数字を含んでいます。

それが成立するためには x <= z <= y . というのも y は最小の数字 > x , z はその間に入ることはできないので、どちらか z = x または z = y . と言う z = x . そうすると、不等式は xB < xD < yC ということは B < D ここで、両方の B と D は同じ桁数です。 しかし、Bは降順にソートされているので、そこに は という文字列は、その数字が大きい文字列ではありません。 したがって B < D . 同じ手順で、もし z = y を持つことはできません。 D < C .

したがって N' は存在できないので、このアルゴリズムでは次に大きい数を正しく見つけることができることになります。