题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
class Solution {
public:
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
int n=nums.size();
dsu d(n);
vector<pair<int,int>> a;
for(int i=0;i<n;i++){
a.emplace_back(nums[i],i);
}
sort(a.begin(),a.end());
for(int i=1;i<n;i++){
if(a[i].first-a[i-1].first<=limit){
d.unite(a[i].second,a[i-1].second);
}
}
unordered_map<int,multiset<int>> g;
for(int i=0;i<n;i++){
g[d.get(i)].insert(nums[i]);
}
for(int i=0;i<n;i++){
int x=*g[d.get(i)].begin();
nums[i]=x;
g[d.get(i)].extract(x);
}
return nums;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla