C++で辞書式順序におけるK番目に小さい数を求める方法

問題概要

2つの整数 n と k が与えられます。1から n までの範囲の整数を「辞書式順序」（数値の大小ではなく、文字列として比較した順序）で並べ替えたとき、k 番目に小さい整数を求めるのがこの問題です。

例えば、n = 14、k = 3 が入力された場合、答えは 11 になります。1から14までの数を辞書式順序で並べると [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9] となるため、3番目の数は 11 だからです。

解法のアプローチ

この問題は、トライ（trie）木の構造をイメージしながら、各接頭辞（プレフィックス）の下にいくつの数が存在するかを効率的に数えることで解決できます。現在注目している数 curr に対して、「隣の数へ横移動する」か「10倍して一桁深く潜る」かを判定しながら、k 番目の数へたどり着きます。

アルゴリズムの手順

1. 関数 findKthNumber(n, k) を定義します。
2. curr を 1 で初期化し、k を 1 減らします。
3. k が 0 になるまで、以下を繰り返します。
   • steps = calcSteps(n, curr, curr + 1) を呼び出し、curr と curr + 1 の間に存在する数の個数を取得します。
   • steps <= k の場合は、curr を先頭とする部分木全体をスキップできます。k -= steps としたうえで curr++ により隣の数へ移動します。
   • そうでない場合は、目的の数が curr の下位に存在するため、curr *= 10 で一桁深く進み、k -= 1 とします。
4. 最終的な curr の値を返します。

calcSteps 関数の役割

calcSteps(nax, n1, n2) は、区間 [n1, n2) に含まれる「nax 以下の数」の個数を返す補助関数です。n1 と n2 を 10 倍ずつしながら、各桁レベルごとの個数を累積していきます。これにより、非常に大きな n に対しても高速に計算が可能になります。

C++実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int findKthNumber(int n, int k) {
      int curr = 1;
      k--;
      while(k){
         int steps = calcSteps(n, curr, curr + 1);
         if(steps <= k){
            k -= steps;
            curr++;
         }else{
            curr *= 10;
            k -= 1;
         }
      }
      return curr;
   }
   int calcSteps(lli nax, lli n1, lli n2){
      int ret = 0;
      while(n1 <= nax){
         ret += min(nax + 1, n2) - n1;
         n1 *= 10;
         n2 *= 10;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findKthNumber(14,3));
}

入力

14,3

出力

11

計算量の評価

時間計算量は O(log² n)、空間計算量は O(1) となります。外側のループは最大でも桁数分（約 log n 回）しか回らず、各ステップで呼ばれる calcSteps も同様に O(log n) 回程度のループで済むため、大きな n に対しても十分実用的な速度で動作します。