Leetcode 6121.裁剪数字后查询第K小的数字

发布于 2022-07-17  61 次阅读

编辑距离

难度： 中等

题目内容

给你一个下标从 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

题目提供代码

class Solution {
public:
vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {

}
};

思路

这道题目是7/17力扣周赛里面出现的一道题目，难度不是很难，但是值得纪念，先说思路，拿到题目之后第一想法就是暴力，因为数据范围很小，把每次要排序的字符串重新拿出来排序就可以了，然后我红红火火恍恍惚惚写完之后一交，TLE！，然后想了很久都没有找出来原因，后来再讨论区看到人家也有类似的问题，然后蹲了三个小时的解答，是函数引用和传参带来的时间问题，然后把sort的cmp函数改成引用之后，40ms就变成了8ms……，总之就是非常神奇，写一篇博客记录一下，顺便下午把sort自定规则的知识点还有关于引用的知识好好复习一遍。

TLE代码

class Solution {
public:
    struct pe
    {
        string aa;
        int b;
    }num[105];
    static bool camp(pe x,pe y)
    //static bool camp(const pe& x, const pe& y)
    {
        if(x.aa!=y.aa)
        return x.aa<y.aa; 
        else
            return x.b<y.b;
    }
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        vector<int> tt;
        int size1 = nums[0].size();
        //queries[0]//第几
        //queries[1]//剩几位
        for(int i=0;i<queries.size();i++)
        {
            for(int j=0;j<nums.size();j++)
            {
                num[j].aa=nums[j].substr(size1-queries[i][1]);
                num[j].b=j;
            }
            sort(num,num+nums.size(),camp);
            tt.push_back(num[queries[i][0]-1].b);
        }
        return tt;
    }
};

AC代码

class Solution {
public:
    struct pe
    {
        string aa;
        int b;
    }num[105];
    //static bool camp(pe x,pe y)
    static bool camp(const pe& x, const pe& y)
    {
        if(x.aa!=y.aa)
        return x.aa<y.aa; 
        else
            return x.b<y.b;
    }
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        vector<int> tt;
        int size1 = nums[0].size();
        //queries[0]//第几
        //queries[1]//剩几位
        for(int i=0;i<queries.size();i++)
        {
            for(int j=0;j<nums.size();j++)
            {
                num[j].aa=nums[j].substr(size1-queries[i][1]);
                num[j].b=j;
            }
            sort(num,num+nums.size(),camp);
            tt.push_back(num[queries[i][0]-1].b
        }
        return tt;
    }
};

题目链接

用代码改变世界