2343-裁剪数字后查询第 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

进阶： 你能使用 基数排序算法 解决此问题吗？这种解法的复杂度又是多少？

Problem: 2343. 裁剪数字后查询第 K 小的数字

[TOC]

解题方法

核心就是基数排序，详细见注释

复杂度

• 时间复杂度: O(mn)

• 空间复杂度: O(mn)

Code

[]

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void sort_radix(int* arr, int* prev, char** nums, int size, int col){
    int temp[10][size+1];
    //  temp的第一位用来存储数组长度
    for(int i=0; i<10; i++) 
        temp[i][0] = 0;
    //  看着挺复杂，其实就是根据前一个数组的顺序来排当前的数组
    for(int i=0; i<size; i++) 
        temp[nums[prev[i]][col]-'0'][++temp[nums[prev[i]][col]-'0'][0]] = prev[i];
    //  按顺序依次赋值
    for(int i=0,k=0; i<10; i++) 
        for(int j=0; j<temp[i][0]; j++) 
            arr[k++] = temp[i][j+1];
}
int* smallestTrimmedNumbers(char ** nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
    //  申请一个数组用来存储每个数位的第k小值所在下标
    int len = strlen(nums[0]), index[len+1][numsSize];
    //  初始化，为了凑下面的遍历
    for(int i=0; i<numsSize; i++) 
        index[0][i] = i;
    //  从后往前依次进行基数排序
    for(int i=1; i<=len; i++)
        sort_radix(index[i],index[i-1],nums,numsSize,len-i);
    int* small = malloc(queriesSize*sizeof(int));
    //  按照排好序的下标数组直接查找
    for(int i=0; i<queriesSize; i++) 
        small[i] = index[queries[i][1]][queries[i][0]-1];
    *returnSize = queriesSize;
    return small;
}