找出[1,n]范围内按照字典排序的最小第k个值
1.题目描述
输入正整数n和k,n>=k，找出[1,n]范围内按照字典排序的最小第k个值。
输入两个正整数n,k
输出一个整数数
实例：
输入：15,3
输出：11
2.题目分析
何为字典顺序？
即，若比较158 和 26，先比较第一个数字，1<2，则125<26
若比较243和257，先比较第一个数字2=2，在比较第二个数字4<5,即243<257
顺序如下：
10 ,100, 11, 12, 13, 14,15,16,17,18,19,2,20,21,22,23......
3.代码
trie树，建立10叉树
public static int lexicalOrder(int n , int k ) {
int curr = 1;
k--;
for (int i = 1; i <= n && k>0; i++) {
if (curr * 10 <= n) {
curr *= 10;
} else if (curr % 10 != 9 && curr + 1 <= n) {
curr++;
}else {
while ((curr / 10) % 10 == 9) {
curr /= 10;
}
curr = curr / 10 + 1;
}
k--;
}
return curr;
}
思路： 如下注释
比如199 10： 字符的变化是 1 10 100 101 102 .. 109 11 110 ..
所以可以看出变化的第一步是 x 10；
而第二步，100 x 10 > 199, 这时候是个位开始 +1， 所以就是 +1；
第三步： 109 下一步加1就会有进位， 110， 但下一个应该是 11， 所以 109 / 10 + 1
第四步： 199 下一步不是200，20 而是2， 故循环判断9， 等于9就除一次10，知道十位不为9；
def k_order(n, k)
curr = 1
k -= 1
index = 1
while (index <= n && k > 0) do
# 字符串递增是后缀加0的顺序，所以递增的时候是先x10
if curr * 10 <= n
curr *= 10
# 个位不为9是排除进位，个位加1是下一阶段的字符递增
elsif curr % 10 != 9 && curr + 1 <= n
curr += 1
else
# 除以10是去掉个位，然后判断十位，如果是9继续循环
# 因为 +1 会进位， 如 199 / 10 = 19
# 不操作的结果是 199 / 10 + 1 = 20 实际应该是2的
while (curr / 10) % 10 == 9 do
curr /= 10
end
curr = curr / 10 + 1
end
k -= 1
index += 1
end
return curr
end
Show Disqus Comments