LeetCode-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

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

解题思路一：最简单的sort()方法

class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        ans = []
        for k,trim in queries:
            tmp=[(num[-trim:],i) for i,num in enumerate(nums)]
            tmp.sort()
            ans.append(tmp[k-1][1])
        return ans

时间复杂度：O(n logn)
空间复杂度：O(n)

解题思路二：基数排序算法，首先记录每个数的下标，让后对这些数进行基数排序，即个位十位百位…。然后需要注意的是存储的是下标，对所有位都排完后结果就是有序的。对个位进行排序那么trim自然等于1，十位对应2，依此类推。取第k小的数就是数组的第[k-1]个元素。

class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        def radix_sort(q, digit):
            tmp = [[] for _ in range(10)]
            for idx in q:
                tmp[int(nums[idx][digit])].append(idx)
            output = []
            for i in tmp:
                if i:
                    output.extend(i)
            return output

        n = len(queries)
        q = list(range(len(nums)))
        mp = {}
        cnt = 1
        for i in range(len(nums[0])-1,-1,-1):
            q = radix_sort(q,i)
            mp[cnt] = q[:]
            cnt += 1
        ans = [0] * n
        for i in range(n):
            k, trim = queries[i]
            ans[i] = mp[trim][k-1]
        return ans

时间复杂度：O(n)
空间复杂度：O(n)

解题思路三：0