LeetCode. 302 weekly games___ 03_ 6121. Query the number smaller than k after cutting the number____ sort

6121. Query the number K Small numbers

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

Solution:

Narrate directly according to the title , Carry out corresponding operations .

• Pay attention to is , I'm looking for k Small numbers correspond to subscripts , We can use custom classes Node, Contains the string s And subscripts index, Use this way Node Array to store nums When the corresponding character after clipping , Store subscripts as well , Next, use custom sorting , Make it follow the string first String The default sorting method , That is, according to the ascii Code in ascending order , When the strings are the same, we will sort them according to the subscript , In this way, we can get an ordered Node Sequence , Then take out the number you want k Just one , At the same time, because we are encapsulated for Node, So the original stored string and the original subscript are both in , So it can be used as answer return ;
• Why encapsulation Node class + Custom sort , Because sorting directly will destroy the subscript structure , So we can only add variable space for persistent storage ;

Code:

class Solution {
    
    public int[] smallestTrimmedNumbers(String[] nums, int[][] queries) {
    
        int numsLen = nums.length;
        int queLen = queries.length;
        int[] answer = new int[queLen];
        
        for(int i=0;i<queLen;i++){
    
            answer[i] = sol(nums,numsLen,queries[i][1],queries[i][0]);
        }
        
        return answer;
    }
    
    public int sol(String[] nums,int numsLen,int trim,int k){
    
        int numLen = nums[0].length();
        Node[] temp = new Node[numsLen];
        for(int i=0;i<numsLen;i++){
    
            temp[i] = new Node();
            temp[i].s = nums[i].substring(numLen - trim);
            temp[i].index = i;
        }
        
        Arrays.sort(temp,(o1,o2) -> {
    
            if(!o1.s.equals(o2.s)){
    
                return o1.s.compareTo(o2.s);
            }
            
            return o1.index - o2.index;
        });
        
        return temp[k - 1].index;
    }
    
    class Node{
    
        int index;
        String s;
    }
}