事情是这样的，有人发帖吐槽了一家外包公司，从起初谈好的21k，三个月试用期8折，到后来突然变成六个月试用期、九折，再到签了offer后每月又改成19.3k，试用期还得再打折，这变脸速度简直让人窒息。
其实，这种外包公司套路并不少见。很多外包喜欢在薪资、试用期等细节上玩文字游戏，先吊你胃口，等你真有意向了再各种变卦。
一些公司甚至会以“拉黑名单”来威胁求职者，搞得像黑社会一样，我觉得这种公司直接pass是最理智的选择。面试环节就这么多花招，进去了会不会更多套路等着你？不如趁早另谋高枝，省心省力。
说到底，外包模式本身并没有原罪，但一些公司不守规则，只顾薅羊毛，让行业整体名声变差。
作为求职者，最重要的是擦亮眼睛，学会识别这些套路：仔细核对合同条款，明确薪资构成，拒绝模棱两可的口头承诺
【备注:文末可领最新资料】
。
好了，我们回归正题，
今天我刷题的时候遇到了一个挺有意思的问题：
给定整数
n
和
k
，问
[1, n]
中字典序的第
k
小的数字是什么
。这题看着挺简单，但是做起来确实需要一点脑筋急转弯，今天我就来和大家聊聊我是怎么一步步解决这个问题的。
字典序排序大家都很熟悉吧，比如
[1, 10, 11, 12, 2, 3]
这样的顺序。题目要我们找到第
k
小的数字，显然直接枚举会很麻烦。
假设
n
特别大，比如
10^9
，你真的想一个个枚举出来排序？CPU都得给你跪了。所以，这题肯定不能蛮干，得动点脑子。
首先我们可以从字典树（Trie）的思路入手。字典序就像是按前缀排序，而字典树正好是处理前缀的高手。比如
1
是前缀，它下面会有
10, 11, 12, ...
，这样一来，我们可以利用字典树的结构快速跳过很多数字，而不是每个数字都去一一比较。
我们可以换个角度思考：假设我们当前在字典树中的某个节点，比如
1
，那么我们能知道以
1
开头的数字有多少个？比如
1, 10, 11, ..., 19
这些数字都以
1
开头。
根据这些数字的个数，我们可以判断
k
是否在当前节点的范围内。如果不在，就可以跳过整个节点，直接移动到下一个节点，效率就大大提高了。
接下来具体看看怎么实现吧。首先我们需要一个函数来计算以某个前缀开头的数字数量。
这个数量不仅仅是单层的，比如
1
不仅包括
10, 11, ..., 19
，还包括更深层的，比如
100, 101, ..., 199
。计算这个数量其实很简单，只要利用范围的上下界逐层扩展就可以了。
public class Solution {
public int findKthNumber(int n, int k) {
int curr = 1; // 从字典树的根节点开始
k--; // 因为根节点1已经占了一位，k要减1
while (k > 0) {
int steps = calculateSteps(n, curr, curr + 1);
if (steps <= k) {
// 如果当前节点下的所有数字数量小于等于k
// 说明第k个数字不在当前这个分支
curr++; // 跳到下一个兄弟节点
k -= steps; // 减去跳过的数字数量
} else {
// 如果当前节点范围内的数字超过了k
// 说明第k个数字在当前分支
curr *= 10; // 往子节点深入
k--; // 减去当前节点本身
}
}
return curr;
}
// 计算以prefix开头的数字的数量
private int calculateSteps(int n, long prefix, long nextPrefix) {
int steps = 0;
while (prefix <= n) {
steps += Math.min(n + 1, nextPrefix) - prefix;
prefix *= 10;
nextPrefix *= 10;
}
return steps;
}
}
代码看起来其实不复杂，重点就在于
calculateSteps
函数，它的作用是快速计算以某个前缀开头的数字数量。比如
prefix = 1
，那么
calculateSteps
会算出以
1
开头的数字有多少。这里用了一个
while
循环，逐层扩大范围，直到超出
n
为止。
接着在主函数里，我们通过比较
k
和
steps
来决定是跳过当前节点还是深入子节点。如果
steps
小于等于
k
，说明第
k
个数字不在当前分支，于是我们直接跳到下一个兄弟节点；否则，就深入当前分支继续找。
这个算法的效率非常高，因为我们每次都在成批地跳过数字，而不是一个个地枚举。复杂度可以控制在
O(log(n))
左右，远比暴力解法快得多。
最后简单跑个测试，看看效果：
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.findKthNumber(13, 2)); // 输出应该是10
}
当
n = 13
和
k = 2
时，字典序是
[1, 10, 11, 12, 13, 2, 3, 4, ...]
，第
k = 2
小的数字是
10
，结果完全正确。
