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

Medium

题目描述

给你一个下标从 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 。
4. 裁剪到剩 2 个数位后，最小数字是 02 ，在下标 0 处。
   注意，裁剪后数字 "02" 的值为 2 。

示例 2：

输入：nums = ["24","37","96","04"], queries = [[2,1],[2,2]]
输出：[3,0]
解释：
1. 裁剪到剩 1 个数位，nums = ["4","7","6","4"] 。第 2 小的数字是下标为 3 的 4 。
   有两个 4 ，但下标 0 处的 4 被认为比下标 3 处的 4 小。
2. 裁剪到剩 2 个数位，nums 不变。第 2 小的数字是 24 。

提示：

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[i].length

解题思路

这个问题要求我们对字符串数组进行多次查询，每次查询需要：

裁剪每个字符串到最右边的指定位数
找到第 k 小的数字的下标
考虑相等时下标小的优先

解题思路：

最直观的方法是模拟每个查询过程：

对于每个查询 [k, trim]，我们首先裁剪所有字符串到最右边 trim 位
创建一个包含 (裁剪后的数字, 原下标) 的数组
对这个数组进行排序，排序规则是：首先按数字大小排序，数字相同时按下标排序
取第 k 小的元素（注意 k 是 1-indexed）

优化思考：

虽然可以使用基数排序等更高效的算法，但考虑到题目的数据规模（nums.length ≤ 100, queries.length ≤ 100），直接模拟已经足够高效。

另一个优化是可以预处理不同裁剪长度的排序结果，但由于查询数量有限，这种优化的收益不大。

实现细节：

字符串裁剪使用 substr 或切片操作
排序时需要自定义比较函数，先比较数值，再比较下标
注意 k 是从 1 开始的，需要转换为 0-indexed

时间复杂度主要由排序决定，每次查询的复杂度为 O(n log n)，其中 n 是数组长度。

代码实现

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        vector<int> result;
        
        for (auto& query : queries) {
            int k = query[0];
            int trim = query[1];
            
            // 创建 (裁剪后的数字, 原下标) 对
            vector<pair<string, int>> trimmed;
            for (int i = 0; i < nums.size(); i++) {
                string trimmedNum = nums[i].substr(nums[i].length() - trim);
                trimmed.push_back({trimmedNum, i});
            }
            
            // 排序：先按数字大小，再按下标
            sort(trimmed.begin(), trimmed.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
                if (a.first.length() != b.first.length()) {
                    return a.first.length() < b.first.length();
                }
                if (a.first != b.first) {
                    return a.first < b.first;
                }
                return a.second < b.second;
            });
            
            // 获取第 k 小的元素的下标（k 是 1-indexed）
            result.push_back(trimmed[k - 1].second);
        }
        
        return result;
    }
};

class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        result = []
        
        for k, trim in queries:
            # 创建 (裁剪后的数字, 原下标) 对
            trimmed = []
            for i, num in enumerate(nums):
                trimmed_num = num[-trim:]  # 取最右边 trim 位
                trimmed.append((trimmed_num, i))
            
            # 排序：先按数字大小，再按下标
            trimmed.sort(key=lambda x: (x[0], x[1]))
            
            # 获取第 k 小的元素的下标（k 是 1-indexed）
            result.append(trimmed[k - 1][1])
        
        return result

public class Solution {
    public int[] SmallestTrimmedNumbers(string[] nums, int[][] queries) {
        var result = new int[queries.Length];
        
        for (int q = 0; q < queries.Length; q++) {
            int k = queries[q][0];
            int trim = queries[q][1];
            
            // 创建 (裁剪后的数字, 原下标) 对
            var trimmed = new List<(string num, int index)>();
            for (int i = 0; i < nums.Length; i++) {
                string trimmedNum = nums[i].Substring(nums[i].Length - trim);
                trimmed.Add((trimmedNum, i));
            }
            
            // 排序：先按数字大小，再按下标
            trimmed.Sort((a, b) => {
                int cmp = string.Compare(a.num, b.num, StringComparison.Ordinal);
                if (cmp == 0) {
                    return a.index.CompareTo(b.index);
                }
                return cmp;
            });
            
            // 获取第 k 小的元素的下标（k 是 1-indexed）
            result[q] = trimmed[k - 1].index;
        }
        
        return result;
    }
}

var smallestTrimmedNumbers = function(nums, queries) {
    const result = [];
    
    for (const [k, trim] of queries) {
        // 创建 [裁剪后的数字, 原下标] 对
        const trimmed = [];
        for (let i = 0; i < nums.length; i++) {
            const trimmedNum = nums[i].slice(-trim); // 取最右边 trim 位
            trimmed.push([trimmedNum, i]);
        }
        
        // 排序：先按数字大小，再按下标
        trimmed.sort((a, b) => {
            if (a[0] !== b[0]) {
                return a[0] < b[0] ? -1 : 1;
            }
            return a[1] - b[1];
        });
        
        // 获取第 k 小的元素的下标（k 是 1-indexed）
        result.push(trimmed[k - 1][1]);
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(Q × N log N × L)	Q 为查询数量，N 为数组长度，L 为字符串长度。每次查询需要 O(N log N) 排序，字符串比较需要 O(L)
空间复杂度	O(N)	存储裁剪后的数字和下标对

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析