LeetCode302场周赛第三题--裁剪数字后查询第 K 小的数字

题目要求：

给你一个下标从 0 开始的字符串数组 nums ，其中每个字符串 长度相等 且只包含数字。

再给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ki, trimi] 。对于每个 queries[i] ，你需要：

将 nums 中每个数字 裁剪 到剩下 最右边 trimi 个数位。
在裁剪过后的数字中，找到 nums 中第 ki 小数字对应的 下标 。如果两个裁剪后数字一样大，那么下标 更小 的数字视为更小的数字。
将 nums 中每个数字恢复到原本字符串。
请你返回一个长度与 queries 相等的数组 answer，其中 answer[i]是第 i 次查询的结果。

提示：

裁剪到剩下 x 个数位的意思是不断删除最左边的数位，直到剩下 x 个数位。
nums 中的字符串可能会有前导 0 。

示例 1：

输入：nums = [“102”,“473”,“251”,“814”], queries = [[1,1],[2,3],[4,2],[1,2]]
输出：[2,2,1,0]
解释：

1. 裁剪到只剩 1 个数位后，nums = [“2”,“3”,“1”,“4”] 。最小的数字是 1 ，下标为 2 。
2. 裁剪到剩 3 个数位后，nums 没有变化。第 2 小的数字是 251 ，下标为 2 。
3. 裁剪到剩 2 个数位后，nums = [“02”,“73”,“51”,“14”] 。第 4 小的数字是 73 ，下标为 1 。
4. 裁剪到剩 2 个数位后，最小数字是 2 ，下标为 0 。
   注意，裁剪后数字 “02” 值为 2 。
   示例 2：

输入：nums = [“24”,“37”,“96”,“04”], queries = [[2,1],[2,2]]
输出：[3,0]
解释：

1. 裁剪到剩 1 个数位，nums = [“4”,“7”,“6”,“4”] 。第 2 小的数字是 4 ，下标为 3 。
   有两个 4 ，下标为 0 的 4 视为小于下标为 3 的 4 。
2. 裁剪到剩 2 个数位，nums 不变。第二小的数字是 24 ，下标为 0 。

提示：

1 <= nums.length <= 100
1 <= nums[i].length <= 100
nums[i] 只包含数字。
所有 nums[i].length 的长度 相同 。
1 <= queries.length <= 100
queries[i].length == 2
1 <= ki <= nums.length
1 <= trimi <= nums[0].length

解题思路：

该题的实质就是求 基数排序第i次的第k小的数值的下标，
用到两个数组，一个二维数组用来存储每一次基数排序后各个值的下标(基数排序从右到左排序)，
这里说的下标就是最原始的值的下标，每通过一次基数排序它们的值的顺序是会变化的，
我们不让它变化，只是通过一个二维数组来记录这些值每次的下标的变化。
另一个二维数组用来模拟基数排序(也叫桶排序，即按每一位来进行排序)。

时间复杂度：

基数排序的时间复杂度为 $O(mn)$ m为数值的位数，n为多少个数

空间复杂度：

因为用到二维数组，所以是 $O(n^2)$级别的

代码实现：

class Solution {
    
public:
    // 使用基数排序，稳定排序
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
    
        int n=nums.size(),m=nums[0].size();
        // rec[i]装的是每轮排序后的数组下标
	    // rec[i][j] 表示基数排序第 i 轮中第 j 小的数对应的下标
        vector<vector<int>> rec(m+1);
        for(int i=0;i<n;++i)rec[0].push_back(i);
        for(int i=1;i<=m;++i){
    
            // 0-9之间的数字对应10个桶
            vector<vector<int>> bucket(10);
            // 估计上一轮的排序结果，然后进行当前位的数组排序，当前位的数字为nums[x][m-i]-'0'
            for(int x:rec[i-1])bucket[nums[x][m-i]-'0'].push_back(x);
            // 将每个桶的排序结果装在rec[i]中，表示当前位排序之后的下标顺序
            for(int j=0;j<10;j++)
                for(int x:bucket[j])
                    rec[i].push_back(x);
        }
        vector<int> res;
        for(const auto& q:queries)
            res.push_back(rec[q[1]][q[0]-1]);
        return res;
    }
};