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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/query-kth-smallest-trimmed-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

仔细分析完题意之后，由于数据量不大，
时间复杂度：O(qmnlogn)，其中 q是数组 queries 的长度，n 是数组 nums 的长度，m 是每个 nums[i] 的长度。每次询问，都需要对一个长为 n 的数组排序，排序共发生 O(nlogn) 次比较，每次比较的耗时为O(m)，故总的时间复杂度为 O(qmnlogn)。
空间复杂度：O(n)。返回值不计入空间复杂度。

这里可以看一下如何在排序中保留原始的下标信息

# 方法一：直接排序
        ans = []
        for k, trim in queries:
            # 因为排序时，下标跟着变，如何在排序中保留原始的下表信息？
            # 把字符串和对应的下标组合成一个pair， 然后对pair排序
            pairs = sorted(zip([num[-trim:] for num in nums], range(len(nums))))
            ans.append(pairs[k - 1][1])
        return ans
1
2
3
4
5
6
7
8

这里还有一个就是，你以为在Python中写成一行很难？其实上面的摇身一变，就变成一行了，但是读起来更困难了，请看

class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        return [sorted(zip([num[-trim:] for num in nums], range(len(nums))))[k - 1][1] for k, trim in queries]
1
2
3

C++实现

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& qs) {
        // 由于要和下标一块排序，所以考验的是C++语法
        int n = nums.size(), m = qs.size();
        vector<pair<string, int>> strs(n);
        for(int i = 0; i < n; i ++) strs[i] = {nums[i], i};
        vector<int> res;

        for(auto& q: qs)
        {
            int k = q[0], trim = q[1];
            // 排序函数里边不加引用过不了，会变慢
            sort(strs.begin(), strs.end(), [&](pair<string, int>& a, pair<string, int>& b){
                // 优先比较数字大小
                for(int i = a.first.size() - trim; i < a.first.size(); i ++){
                    if(a.first[i] < b.first[i])
                        return true;
                    else if(a.first[i] > b.first[i])
                        return false;
                }
                // 其次比较下标
                return a.second < b.second;
            });

            res.push_back(strs[k-1].second);
        } 
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30