C++ 中按字典顺序查找第 k 个小数
c++server side programmingprogramming
假设有两个值 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。
为了解决这个问题，我们将遵循以下步骤 −
- Define a function findKthNumber(), this will take n, k,
- curr := 1
- (decrease k by 1)
- while k is non-zero, do −
- steps := call the function calcSteps(n, curr, curr + 1)
- if steps <= k, then −
- k := k - steps
- (increase curr by 1)
- Otherwise
- curr := curr * 10
- k := k - 1
- return curr
- Define a function calcSteps(), this will take nax, n1, n2,
- ret := 0
- while n1 <= nax, do −
- ret := ret + minimum of nax + 1 and 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
