C ++中按字典顺序最小的第K个

假设我们有两个值n和k。在字典上，我们必须找到第k个最小的整数，范围是1到n。因此，如果输入像n = 14且k = 3，则输出将为11，因为序列将为[1、10、11、12、13、14、2、3、4、5、6、7 ，8，9]，则第k个数字为11。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数findKthNumber()，它将花费n，k，

• curr：= 1

• （将k减1）

• 当k不为零时，执行-

• curr：= curr * 10

• k：= k-1

• k：= k-步骤

• （增加curr 1）

• steps：=调用函数calcSteps（n，curr，curr + 1）

• 如果步数<= k，则-

• 除此以外

• 返现

• 定义一个函数calcSteps()，它将使用nax，n1，n2，

• ret：= 0

• 当n1 <= nax时，-

• ret：= ret +纳克斯最小值+ 1和n2 – n1

• n1：= n1 * 10

• n2：= n2 * 10

• 返回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