The third question of leetcode 302 weekly Games -- query the number with the smallest k after cutting the number

Subject requirements ：

I'll give you a subscript from 0 Starting string array nums , Each of these strings Equal length And contains only numbers .

Give you another subscript from 0 Start with a two-dimensional integer array queries , among queries[i] = [ki, trimi] . For each queries[i] , You need ：

take nums Each number in tailoring To the rest Far right trimi One digit .
In the cropped numbers , find nums pass the civil examinations ki Small numbers correspond to Subscript . If the two cut numbers are the same , So subscript smaller The number of is regarded as a smaller number .
take nums Restore each number in to the original string .
Please return a length and queries Equal array answer, among answer[i] It's No i Results of this query .

Tips ：

Cut to the rest x Digit means constantly deleting the leftmost digit , Until the rest x One digit .
nums The string in may have a leading 0 .

Example 1：

Input ：nums = [“102”,“473”,“251”,“814”], queries = [[1,1],[2,3],[4,2],[1,2]]
Output ：[2,2,1,0]
explain ：

1. Cut to just 1 After a few digits ,nums = [“2”,“3”,“1”,“4”] . The smallest number is 1 , Subscript to be 2 .
2. Cut to the left 3 After a few digits ,nums There is no change . The first 2 The small number is 251 , Subscript to be 2 .
3. Cut to the left 2 After a few digits ,nums = [“02”,“73”,“51”,“14”] . The first 4 The small number is 73 , Subscript to be 1 .
4. Cut to the left 2 After a few digits , The minimum number is 2 , Subscript to be 0 .
   Be careful , Number after clipping “02” The value is 2 .
   Example 2：

Input ：nums = [“24”,“37”,“96”,“04”], queries = [[2,1],[2,2]]
Output ：[3,0]
explain ：

1. Cut to the left 1 One digit ,nums = [“4”,“7”,“6”,“4”] . The first 2 The small number is 4 , Subscript to be 3 .
   There are two 4 , Subscript to be 0 Of 4 Regarded as less than the subscript is 3 Of 4 .
2. Cut to the left 2 One digit ,nums unchanged . The second smallest number is 24 , Subscript to be 0 .

Tips ：

1 <= nums.length <= 100
1 <= nums[i].length <= 100
nums[i] Numbers only .
all nums[i].length The length of identical .
1 <= queries.length <= 100
queries[i].length == 2
1 <= ki <= nums.length
1 <= trimi <= nums[0].length

Their thinking ：

The essence of this question is to find The cardinality order is i The second time k Subscript of small value ,
Use two arrays , A two-dimensional array is used to store the subscripts of each value after each cardinality sorting ( Cardinality sort from right to left ),
The subscript here is the subscript of the original value , The order of their values will change every time they are sorted by cardinality ,
We won't let it change , Just use a two-dimensional array to record the subscript changes of these values every time .
Another two-dimensional array is used to simulate cardinality sorting ( Also called bucket sorting , That is, sort by each bit ).

Time complexity ：

The time complexity of Radix sorting is $O(mn)$ m Is the number of digits of the value ,n How many numbers

Spatial complexity ：

Because two-dimensional arrays are used , So it is $O(n^2)$ Grade

Code implementation ：

class Solution {
    
public:
    //  Sort using cardinality , Stable sequencing 
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
    
        int n=nums.size(),m=nums[0].size();
        // rec[i] Installed is the array subscript after each round of sorting 
	    // rec[i][j]  Indicates the cardinality order  i  In the middle of the round  j  The subscript corresponding to a small number 
        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 The numbers between correspond 10 A barrel 
            vector<vector<int>> bucket(10);
            //  Estimate the ranking result of the last round , Then sort the array of current bits , The current digit is nums[x][m-i]-'0'
            for(int x:rec[i-1])bucket[nums[x][m-i]-'0'].push_back(x);
            //  Put the sorting results of each bucket in rec[i] in , Indicates the subscript order after the current bit sorting 
            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;
    }
};