C++ 中字典序第 K 小的数

假设我们有两个值 n 和 k。我们需要找到 1 到 n 范围内字典序第 k 小的整数。例如，如果输入为 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 不为零时，执行以下操作：
    • steps := 调用函数 calcSteps(n, curr, curr + 1)
    • 如果 steps <= k，则：
      • k := k - steps
      • (将 curr 加 1)
    • 否则
      • curr := curr * 10
      • k := k - 1
    • 返回 curr
  • 定义一个函数 calcSteps()，它将接收 nax、n1、n2 作为参数。
  • ret := 0
  • 当 n1 <= nax 时，执行以下操作：
    • ret := ret + min(nax + 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

更新于: 2020-06-01

722 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告