html5 微网站模版,广州专业网站建设报价,优化公司网站,北京城乡住房建设厅网站Problem: 2948. 交换得到字典序最小的数组 文章目录 题目思路Code 题目
给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。
在一次操作中#xff0c;你可以选择任意两个下标 i 和 j#xff0c;如果 满足 |nums[i] - nums[j]| limit #xff0c;则交换… Problem: 2948. 交换得到字典序最小的数组 文章目录 题目思路Code 题目
给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。
在一次操作中你可以选择任意两个下标 i 和 j如果 满足 |nums[i] - nums[j]| limit 则交换 nums[i] 和 nums[j] 。
返回执行任意次操作后能得到的 字典序最小的数组 。
如果在数组 a 和数组 b 第一个不同的位置上数组 a 中的对应字符比数组 b 中的对应字符的字典序更小则认为数组 a 就比数组 b 字典序更小。例如数组 [2,10,3] 比数组 [10,2,3] 字典序更小下标 0 处是两个数组第一个不同的位置且 2 10 。
示例 1
输入nums [1,5,3,9,8], limit 2 输出[1,3,5,8,9] 解释执行 2 次操作
交换 nums[1] 和 nums[2] 。数组变为 [1,3,5,9,8] 。交换 nums[3] 和 nums[4] 。数组变为 [1,3,5,8,9] 。 即便执行更多次操作也无法得到字典序更小的数组。 注意执行不同的操作也可能会得到相同的结果。
思路 首先我们先将 nums数组每一个元素和他对应的index进行捆绑 (i,nums[i]) 。 因为题目要求任意的 i,j可以交换满足 $ |nums[i| - num[j] limit $这样我们就可以这样想这样的i,j肯定是在一个组内并且组内满足相邻元素相差不超过 limit 比如 nums [1,7,6,18,2,1] ,limit 3 排序之后相差3的 1 2 1 7 ,6 18 然后每个分组内排序再回填到原来的数组中有点类似希尔排序。 Code
class Solution {
public:vectorint lexicographicallySmallestArray(vectorint nums, int limit) {int n nums.size() ; vectorint ans(nums) ; vectorpairint,int p(n) ;// 带有下标的 for(int i 0 ;in ; i ) {p[i] (make_pair(i,nums[i])) ; }sort(p.begin(),p.end(),[](const auto a, const auto b) {return a.second b.second; // 按照 nums[i] 的值升序排序}) ; // 吧所有的元素切成若干子段子段内的相邻元素之差不超过limit for(int i 0 ; in ; ) {int j i ; while(j1n (p[j1].second - p[j].second) limit ) {j ; }// 组内排序sort(p.begin() i, p.begin() j 1, [](const auto a, const auto b) {return a.first b.first;});//填充答案vectorint temp(j - i 1);for (int k 0; k j - i; k) {temp[k] ans[p[i k].first];}sort(temp.begin(), temp.end());for (int k 0; k j - i; k) {ans[p[i k].first] temp[k];}//处理下一段i j1 ; }return ans ; }
};
