leetcode 440.K-th Smallest in Lexicographical Orderのk番目の辞書順の数字+できません
5149 ワード
Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
Input: n: 13 k: 2
Output: 10
Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
実はこの問題leetcode 386.Lexicographical Numbersの辞書の順序の配列と同じですが、本題はk番目の辞書の順序の数字がどれなのかを求めて、このようにするとタイムアウトします
辞書の順序の配列をよく見ると、これは10叉木Denary Treeであり、各ノードのサブノードが10個であってもよく、例えば数字1のサブノードが10から19であり、数字10のサブノードが100から109であってもよいが、nの大きさの制限のため、構成されているのは10叉木ではないことがわかる.問題の中で与えられた例を分析すると,数字1のサブノードは4つ(10,11,12,13)あるが,後の数字2から9にはサブノードがないので,この問題は実際には十叉木を先に巡る問題になり,難点は各ノードのサブノードの個数をどのように計算するか,kでサブノードの個数を減算し続け,kが0に減少すると、現在位置の数字が求められる.次に、サブノードの数を求める方法を見てみましょう.例えば、数字1と数字2です.辞書の遍歴順で1から2までに何個の数字が必要かを要求します.まず、1自体の数字をstepに追加します.それから、範囲を10倍に拡大し、範囲を10から20にする前にします.しかし、nの大きさを考慮すると、nは13なので、4つのサブノードしかありません.このように、数字1から数字2まで5つの数字を通過する必要があることを知っています.そして、stepがk以下であるかどうかを見てみましょう.もしそうであれば、curは1を増やし、kはstepを減らします.そうでなければ、要求された数字がサブノードにあることを説明します.この場合、curに10を乗算し、kは1を減算します.このようにして、kが0になるまでループを押し出します.この場合、curは求められます.
コードは次のとおりです.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
Input: n: 13 k: 2
Output: 10
Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
実はこの問題leetcode 386.Lexicographical Numbersの辞書の順序の配列と同じですが、本題はk番目の辞書の順序の数字がどれなのかを求めて、このようにするとタイムアウトします
辞書の順序の配列をよく見ると、これは10叉木Denary Treeであり、各ノードのサブノードが10個であってもよく、例えば数字1のサブノードが10から19であり、数字10のサブノードが100から109であってもよいが、nの大きさの制限のため、構成されているのは10叉木ではないことがわかる.問題の中で与えられた例を分析すると,数字1のサブノードは4つ(10,11,12,13)あるが,後の数字2から9にはサブノードがないので,この問題は実際には十叉木を先に巡る問題になり,難点は各ノードのサブノードの個数をどのように計算するか,kでサブノードの個数を減算し続け,kが0に減少すると、現在位置の数字が求められる.次に、サブノードの数を求める方法を見てみましょう.例えば、数字1と数字2です.辞書の遍歴順で1から2までに何個の数字が必要かを要求します.まず、1自体の数字をstepに追加します.それから、範囲を10倍に拡大し、範囲を10から20にする前にします.しかし、nの大きさを考慮すると、nは13なので、4つのサブノードしかありません.このように、数字1から数字2まで5つの数字を通過する必要があることを知っています.そして、stepがk以下であるかどうかを見てみましょう.もしそうであれば、curは1を増やし、kはstepを減らします.そうでなければ、要求された数字がサブノードにあることを説明します.この場合、curに10を乗算し、kは1を減算します.このようにして、kが0になるまでループを押し出します.この場合、curは求められます.
コードは次のとおりです.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class Solution
{
public:
int findKthNumber(int n, int k)
{
int cur = 1;
--k;
while (k > 0)
{
long long step = 0, first = cur, last = cur + 1;
while (first <= n)
{
step += min((long long)n + 1, last) - first;
first *= 10;
last *= 10;
}
if (step <= k)
{
++cur;
k -= step;
}
else
{
cur *= 10;
--k;
}
}
return cur;
}
int findKthNumberByLoop(int n, int k)
{
vector<int> res(n, 0);
int cur = 1;
for (int i = 0; i < n; i++)
{
res[i] = cur;
if (cur * 10 <= n)
cur *= 10;
else
{
if (cur >= n)
cur /= 10;
cur += 1;
while (cur % 10 == 0)
cur /= 10;
}
}
return res[k - 1];
}
};