C++の辞書式順序でK番目に小さい

2つの値nとkがあるとします。辞書式順序で1からnの範囲でk番目に小さい整数を見つける必要があります。したがって、入力がn=14およびk=3の場合、シーケンスは[1、10、11、12、13、14、2、3、4、5、6、7になるため、出力は11になります。 、8、9]の場合、k番目の数値は11です。

これを解決するには、次の手順に従います-

• 関数findKthNumber（）を定義します。これには、n、k、
が必要です。
• curr：=1
• （kを1つ減らす）
• kがゼロ以外の場合、-
  を実行します。
  • steps：=関数calcSteps（n、curr、curr + 1）を呼び出します
  • ステップ<=kの場合、-
    • k：=k-ステップ
    • （currを1増やします）
  • それ以外の場合
    • curr：=curr * 10
    • k：=k-1
  • リターンカー
• 関数calcSteps（）を定義します。これには、nax、n1、n2、
が必要です。
• ret：=0
• n1 <=naxの場合、-
  を実行します
  • ret：=ret+最小のnax+1およびn2– n1
  • n1：=n1 * 10
  • n2：=n2 * 10
• return ret

理解を深めるために、次の実装を見てみましょう-

例

#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