https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/
我没做出来。还是脑子不够清醒。
下面这个解法真的很棒很棒。
https://discuss.leetcode.com/topic/64442/easy-to-understand-js-solution
原理可以参照下面这个看，就更清楚了
https://discuss.leetcode.com/topic/64462/c-python-0ms-o-log-n-2-time-o-1-space-super-easy-solution-with-detailed-explanations
我开始只是想第一个数字找到个数。实际上第一个找到之后，可以仍然保留作为前缀，每次看相同前缀的数字存在多少个。
这个过程，代码写的好艰辛。
虽然从上面看了思路，但是真正写的时候，还是发现有大大小小的坑。很多细节和corner case需要处理。
开始听着音乐写，头越来越晕，还是不行。
1. 使用了一个count来获得前缀是 xyz，并且 <=n 的情况下，有多少次出现。
注意使用 (prefix+1) * step <= n+1 来检查，并且在循环结束后检查一下，是否需要加上最后余下的一些个数（具体见下面代码的实现）。
这个结果会用来每次对于k进行减除。而如果count是小于等于k的情况，就保留这个前缀，因为这个前缀一定会出现在最后结果中。然后再下一轮循环。
2. 对于0的处理，我的代码里面用了 prefix==0直接返回count为0来处理。并且检查是否正好k==1返回前缀prefix作为结果时，只针对prefix>0.
3. 对于 xx 和 xxi 的区分（其中i是0-9的数字）。仔细分析，发现总是有一个xx在最前面，不需要加i。并且占了一位。
所以对于k最后是1的情况，直接返回xx就可以了；如果k>1，那就把xx所占的一位减掉，然后再加后缀来检查。
最后，count函数对于 xx * 10 + i 还溢出了，需要用long类型才可以。
代码如下：
package com.company; //https://discuss.leetcode.com/topic/64442/easy-to-understand-js-solution
//https://discuss.leetcode.com/topic/64462/c-python-0ms-o-log-n-2-time-o-1-space-super-easy-solution-with-detailed-explanations class Solution { // 开始prefix写成 int,超出了
private int getCount(int n, long prefix) {
if (prefix == 0) {
return 0;
} int count = 0;
int step = 1;
while ((prefix+1) * step <= n+1) {
count += step;
step *= 10;
}
if (prefix * step <= n) {
count += n + 1 - prefix * step;
}
return count;
} public int findKthNumber(int n, int k) { int prefix = 0; while (k > 0) {
if (prefix != 0) {
if (k == 1) {
return prefix;
}
else {
k--;
}
} for (int i=0; i<10; i++) { int count = getCount(n, prefix*10+i);
if (k > count) {
k -= count;
}
else {
prefix = prefix * 10 + i;
break;
}
}
}
return prefix;
}
} public class Main { public static void main(String[] args) {
// write your code here
System.out.println("Hello");
Solution solution = new Solution(); int n = 681692778, k = 351251360;
int ret = solution.findKthNumber(n, k);
System.out.printf("Result is %d\n", ret); }
}