说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是处于什么原因，算法学习需要持续保持，今天让我们一起来看看这一道题目————
裁剪数字后查询第 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
思路分析
首先我们要理解题目的意思，题目参数中的queries为一个二维数组，其中queries[i]为一次询问queries[i][1]表示将数字裁剪到剩下queries[i][1]位，queries[i][0]表示将nums中的数字裁剪成剩下queries[i][1]位后获取第queries[i][0]小数字的下标。
- 如示例一
nums = ["102","473","251","814"] queries[2] 为[4,2] 首先我们将nums裁剪剩下queries[2][1]位，也即是2位，得到nums = ["02","73","51","14"] 其中第queries[2][0]小，也即是第4小的数字为73，其下标为1 所以我们应该要返回的结果为1
理解了题目之后我们便可以开始解题了，这里我使用一个哈希表将每一种情况都记录下来，后面询问的时候就可以直接从哈希表中取出结果，具体如下：
- 获取截取后的数字列表
key为截取数字长度，value[0]为数字的下标，value[1]为截取的数字。
let map = {}; for(let i = 0; i < nums.length; i++){ let str = ''; for(let j = nums[i].length - 1; j >= 0; j--){ let ind = nums[i].length - j; str = nums[i][j] + str; if(!map[ind]) map[ind] = []; map[ind].push([i,str]); } }
得到结果如下
{ '1': [ [ 0, '2' ], [ 1, '3' ], [ 2, '1' ], [ 3, '4' ] ], '2': [ [ 0, '02' ], [ 1, '73' ], [ 2, '51' ], [ 3, '14' ] ], '3': [ [ 0, '102' ], [ 1, '473' ], [ 2, '251' ], [ 3, '814' ] ] }
- 将数字列表进行排序
将的得到的结果按规则进行排序，数字从小到大进行排序，如果两个裁剪后数字一样大，那么下标 更小 的数字视为更小的数字。
for(let key in map){ map[key] = map[key].sort((a,b)=>{ if(a[1] == b[1]) return a[0] - b[0]; return a[1].localeCompare(b[1]); }) }
得到结果如下
{ '1': [ [ 2, '1' ], [ 0, '2' ], [ 1, '3' ], [ 3, '4' ] ], '2': [ [ 0, '02' ], [ 3, '14' ], [ 2, '51' ], [ 1, '73' ] ], '3': [ [ 0, '102' ], [ 2, '251' ], [ 1, '473' ], [ 3, '814' ] ] }
- 遍历取出答案
let res = []; for(let i = 0; i < queries.length; i++){ let value = map[queries[i][1]][queries[i][0] - 1][0]; res.push(value); }
完整AC代码如下：
AC代码
/** * @param {string[]} nums * @param {number[][]} queries * @return {number[]} */ var smallestTrimmedNumbers = function(nums, queries) { let map = {}; for(let i = 0; i < nums.length; i++){ let str = ''; for(let j = nums[i].length - 1; j >= 0; j--){ let ind = nums[i].length - j; str = nums[i][j] + str; if(!map[ind]) map[ind] = []; map[ind].push([i,str]); } } for(let key in map){ map[key] = map[key].sort((a,b)=>{ if(a[1] == b[1]) return a[0] - b[0]; return a[1].localeCompare(b[1]); }) } let res = []; for(let i = 0; i < queries.length; i++){ let value = map[queries[i][1]][queries[i][0] - 1][0]; res.push(value); } return res; };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
