Re: [閒聊] 每日leetcode
2948. Make Lexicographically Smallest Array by Swapping Elements
## 思路
先產生排序過的 {num, idx}
用UnionFind把可以互換的idx都加到同group
## Code
```cpp
class UnionFind {
public:
UnionFind(int size) {
rank_.resize(size, 1);
root_.resize(size, 0);
for (int i=0; i<size; ++i) {
root_[i] = i;
}
}
int findP(int x) {
if (root_[x] != x) {
root_[x] = findP(root_[x]);
}
return root_[x];
}
bool unionP(int x, int y) {
int rx = findP(x), ry = findP(y);
if (rx == ry) return false;
if (rank_[rx] >= rank_[ry]) {
root_[ry] = rx;
rank_[rx] += rank_[ry];
} else {
root_[rx] = ry;
rank_[ry] += rank_[rx];
}
return true;
}
private:
vector<int> root_;
vector<int> rank_;
};
class Solution {
public:
vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
int n = nums.size();
UnionFind uf(n);
vector<pair<int, int>> arr;
for (int i=0; i<n; ++i) {
arr.push_back({nums[i], i});
}
sort(arr.begin(), arr.end());
for (int i=1; i<n; ++i) {
if (arr[i].first - arr[i-1].first <= limit) {
uf.unionP(arr[i].second, arr[i-1].second);
}
}
unordered_map<int, queue<int>> groups;
for (auto& [num, idx]: arr) {
groups[uf.findP(idx)].push(num);
}
vector<int> res;
for (int i=0; i<n; ++i) {
int root = uf.findP(i);
res.push_back(groups[root].front());
groups[root].pop();
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 86.48.13.191 (日本)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737771072.A.02A.html
討論串 (同標題文章)
完整討論串 (本文為第 1306 之 1552 篇)：