Readme

2343.Query-Kth-Smallest-Trimmed-Number

本题的数据规模非常小，对每个query进行暴力处理也是可以过的。

这里介绍一个比较优秀的“基数排序”的算法。我们令ans[i][j]表示只保留i位数字时，排列第j小的元素的原始index。

我们先考虑只保留一位数字的情况。假设此时的元素排序后是这些：0(x),0(x),1(x),1(x),2(x),3(x),3(x),3(x),4(x),4(x)...其中括号里面的是对应的index，具体数字不重要，他们构成了ans[1][j].

然后我们考虑只保留两位数字的情况。这些元素的第二位数字只有10种可能0~9，并且我们知道第二位数字是排序的primary key。这里我们就有一个技巧能够加快排序。我们构造10个bucket。我们将第一轮有序的元素按照他们各自的第二位数字，按照先后顺序扔进不同的bucket里面。此时就有一个非常好的性质：不同的bucket之间的元素必然是有序的（bucket小靠前）；同一个bucket内的元素也是有序的（先扔进去的是第一轮里的较小元素，必然会靠前）。此时我们相当于只用了线性的时间就实现了所有元素的排序。我们此时将所有元素按照bucket的顺序和bucket内部的先后顺序访问一遍，就得到了ans[2][j].

以此类推，我们可以实现保留三位数字的元素的排序ans[3][j]，等等。

最终我们对于每个query，我们返回的其实就是ans[trim][k-1].