admin管理员组文章数量:1647602
本文涉及知识点
排序
离线查询
LeetCode2343. 裁剪数字后查询第 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 个数位后,nums = [“2”,“3”,“1”,“4”] 。最小的数字是 1 ,下标为 2 。
- 裁剪到剩 3 个数位后,nums 没有变化。第 2 小的数字是 251 ,下标为 2 。
- 裁剪到剩 2 个数位后,nums = [“02”,“73”,“51”,“14”] 。第 4 小的数字是 73 ,下标为 1 。
- 裁剪到剩 2 个数位后,最小数字是 2 ,下标为 0 。
注意,裁剪后数字 “02” 值为 2 。
示例 2:
输入:nums = [“24”,“37”,“96”,“04”], queries = [[2,1],[2,2]]
输出:[3,0]
解释: - 裁剪到剩 1 个数位,nums = [“4”,“7”,“6”,“4”] 。第 2 小的数字是 4 ,下标为 3 。
有两个 4 ,下标为 0 的 4 视为小于下标为 3 的 4 。 - 裁剪到剩 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
进阶:你能使用 基数排序(shell sort)算法 解决此问题吗?这种解法的复杂度又是多少?
排序+离线查询
n = nums.size()
m = nums[0].length
我们对nums的下标indexs排序:
第0轮排序标准 :nums[i][n-1]小的标下在前,相等则i小的在前。 此时可以处理trimi=1的查询。
第1轮在第0轮基础上排序,排序标准:nums[i][n-1-1]小的下标在前,相等则不边。此时可以处理trimi=2的查询。
第2轮在第1轮基础上排序,排序标准:nums[i][n-1-2]小的下标在前,相等则不边。此时可以处理trimi=3的查询。
第3轮在第2轮基础上排序,排序标准:nums[i][n-1-3]小的下标在前,相等则不边。此时可以处理trimi=4的查询。
⋮
\vdots
⋮
vector<vector> queIndexs,queIndexs[i]记录所有trimi为i的下标。
使用的排序方法必须是稳定的排序算法,这样才能保证相等的时候,顺序不变。
注意:第0轮之前,已经按下标排序了,所以第0轮,相等无需处理。
时间复杂度: O(mnlogn)
stable_sort(稳定排序函数)
与sort的区别:sort更类似于快速排序的思想,而stable_sort用得是归并排序的思路
当数据都相同时,他不会打乱原有的顺序,所以更加稳定例如:有两个相同的数A和B,在sort排序后B有可能会跑到A的前面,但是stable_sort则不会打乱原有顺序
代码
核心代码
class Solution {
public:
vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
const int N = nums.size();
const int M = nums.front().size();
vector<vector<int>> queIndexs(M + 1);
for (int i = 0; i < queries.size();i++) {
queIndexs[queries[i][1]].emplace_back(i);
}
vector<int> indexs(N),ret(queries.size());
iota(indexs.begin(), indexs.end(), 0);
for (int i = 0; i < M; i++) {
const int cur = M - 1 - i;
stable_sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return nums[i1][cur] < nums[i2][cur]; });
for (const auto& inx : queIndexs[i + 1]) {
ret[inx] = indexs[queries[inx][0] - 1];
}
}
return ret;
}
};
单元测试
vector<string> nums;
vector<vector<int>> queries;
TEST_METHOD(TestMethod11)
{
nums = { "102","473","251","814" }, queries = { {1,1},{2,3},{4,2},{1,2} };
auto res = Solution().smallestTrimmedNumbers(nums, queries);
AssertEx({2, 2, 1, 0}, res);
}
TEST_METHOD(TestMethod12)
{
nums = { "24","37","96","04" }, queries = { {2,1},{2,2} };
auto res = Solution().smallestTrimmedNumbers(nums, queries);
AssertEx({ 3,0 }, res);
}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
版权声明:本文标题:【C++稳定排序 离线查询】2343. 裁剪数字后查询第 K 小的数字|1651 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1729489449a1202428.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论