2948. 交换得到字典序最小的数组 - 力扣（LeetCode）
代码参考：
并查集【C++数据结构进阶】玩转并查集：从原理到实战，C++ 实现与高频面试题全解析_并查集c++-CSDN博客
题目
给你一个下标从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] 。 即便执行更多次操作，也无法得到字典序更小的数组。 注意，执行不同的操作也可能会得到相同的结果。
示例 2：
输入：nums = [1,7,6,18,2,1], limit = 3输出：[1,6,7,18,1,2]解释：执行 3 次操作： - 交换 nums[1] 和 nums[2] 。数组变为 [1,6,7,18,2,1] 。 - 交换 nums[0] 和 nums[4] 。数组变为 [2,6,7,18,1,1] 。 - 交换 nums[0] 和 nums[5] 。数组变为 [1,6,7,18,1,2] 。 即便执行更多次操作，也无法得到字典序更小的数组。
示例 3：
输入：nums = [1,7,28,19,10], limit = 3输出：[1,7,28,19,10]解释：[1,7,28,19,10] 是字典序最小的数组，因为不管怎么选择下标都无法执行操作。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= limit <= 109
思路
目标是得到字典序最小的数组，即最小的数，也就是尽可能让更小值放在更前面。那么是否可以考虑分别维护不同的可交换小组（因为可交换元素之间也符合交换率），然后小组中用某种方法维护“值”和“下标”两个属性，那么就可以将对应的数据由小到大重新排入对应的下标之中，得出的结果自然也就是最小的了。
那么该怎么构造这样的数据结构就是主要问题了。
没想出来比较好的解决方案偷偷看了一下提示——并查集，又得开始补习了（感谢【C++数据结构进阶】玩转并查集：从原理到实战，C++ 实现与高频面试题全解析_并查集c++-CSDN博客，非常清楚地解释了并查集的原理和构造方法，我基本就是纯copy）。这是一个维护“相关”关系的数据结构，时空复杂度都是O(n)的。参照这个思路，我们可以维护一个和输入数组等长的一维数组，初始化为-1，利用双重循环遍历数组，将满足条件的数组通过下标连接起来，连接的方式为，若两者满足限制条件，则下标较小的节点为下标较大的节点的父节点，这样我们就可以通过双重循环分出不同的独立的可交换小组。
新的问题又出现了，现在得到了几个独立的可交换小组，怎么按小到大的顺序将他们交换呢？本来想自定义sort的比较函数的，但是排序结果一直不符合预期——因为sort逻辑主要是基于归并排序的逻辑，相等的元素不是位置保持不变，而是被集体往后挪动，只把更小的元素往前放，所以单纯的sort无法实现不同组不比较的逻辑。
那么只能通过哈希表分别对不同的组维护一个数组再排序了，但是还是超时了，因为出现了超多分组，显然如果小组内有多个元素，那么肯定需要排序，如果没有多个元素，那就不必构造哈希表排序了。
既然不行，估计是排序上开销太大了，因为插入的同时就可以排序了，而不用插完再排序一次，所以不妨直接建立小顶堆而不是vector，这样插入的同时就做好了排序了。
好的，一系列优化之后，还是超时，说明瓶颈在前面建立并查集的过程中。
class Solution { public: int FindRoot(vector<int> &ufs, int index) { if(index < 0 || index >= ufs.size()) { throw invalid_argument("index out of range."); } // 找到根节点 int root = index; while(ufs[root] >= 0) { root = ufs[root]; } // 路径压缩：将路径上所有节点挂靠到根节点上 while(ufs[index] >= 0) { int parent = ufs[index]; ufs[index] = root; index = parent; } return root; } bool Union(vector<int> &ufs, int x, int y) { int root1 = FindRoot(ufs, x); int root2 = FindRoot(ufs, y); if(root1 == root2) return false; // 将较小集合合并到较大集合中，令root1为较大集合（这里两个root的都是存的负数，所以越小越大） if(root1 > root2) swap(root1, root2); ufs[root1] += ufs[root2]; ufs[root2] = root1; return true; } vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) { // 目标是得到字典序最小的数组，即最小的数，也就是尽可能让更小值放在更前面 int n = nums.size(); vector<int> ufs(n, -1); for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { if(abs(nums[i]-nums[j]) <= limit) { Union(ufs, i, j); } } } unordered_map<int, priority_queue<int, vector<int>, greater<int>>> groups; unordered_map<int, priority_queue<int, vector<int>, greater<int>>>::iterator iter; // 建立小组集合 for(int i = 0; i < n; i++) { if(ufs[i] < 0) { if(abs(ufs[i]) > 1) groups[i].push(nums[i]); } else groups[FindRoot(ufs, i)].push(nums[i]); } for(int i = 0; i < n; i++) { if(ufs[i] == -1) continue; int groupNo = FindRoot(ufs, i); nums[i] = groups[groupNo].top(); groups[groupNo].pop(); } return nums; } };我太菜了，还是看了分析，因为现在的并查集构造部分是O(n^2α(n))的，还是太大了，目标是再进行一次降维。那么只能考虑把输入数据构造成一个新的能够更方便做并查集的数据，因为看了分析，我们可以直接知道，要把数据先排序，这样就只用看相邻元素就可以知道是不是同一组了，这样就可以达到O(nα(n))的复杂度构造并查集了。
所以不妨构造一个形如pair<value, index>的数组，然后对根据value，index进行排序，这样我们就可以得到一个按value升序，同value按index升序的数组。再基于这个数组遍历构造并查集，剩下的部分沿用原来的方案即可。
只能说太巧妙了，这题中等难度感觉屈才了，感觉蛮考验数据结构的设计的，相比于算法上困难的题目，这个题目感觉更考验巧思或者工程能力。
代码实现
class Solution { public: int FindRoot(vector<int> &ufs, int index) { if(index < 0 || index >= ufs.size()) { throw invalid_argument("index out of range."); } // 找到根节点 int root = index; while(ufs[root] >= 0) { root = ufs[root]; } // 路径压缩：将路径上所有节点挂靠到根节点上 while(ufs[index] >= 0) { int parent = ufs[index]; ufs[index] = root; index = parent; } return root; } bool Union(vector<int> &ufs, int x, int y) { int root1 = FindRoot(ufs, x); int root2 = FindRoot(ufs, y); if(root1 == root2) return false; // 将较小集合合并到较大集合中，令root1为较大集合（这里两个root的都是存的负数，所以越小越大） if(root1 > root2) swap(root1, root2); ufs[root1] += ufs[root2]; ufs[root2] = root1; return true; } vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) { // 目标是得到字典序最小的数组，即最小的数，也就是尽可能让更小值放在更前面 int n = nums.size(); vector<int> ufs(n, -1); vector<pair<int, int>> sortedNums(n); for(int i = 0; i < n; i++) { sortedNums[i] = make_pair(nums[i], i); } sort(sortedNums.begin(), sortedNums.end(), [](pair<int,int> a, pair<int,int> b) { if(a.first == b.first) return a.second < b.second; return a.first < b.first; }); // 构造并查集 for(int i = 1; i < n; i++) { if(abs(sortedNums[i].first-sortedNums[i-1].first) <= limit) { Union(ufs, sortedNums[i].second, sortedNums[i-1].second); } } unordered_map<int, priority_queue<int, vector<int>, greater<int>>> groups; unordered_map<int, priority_queue<int, vector<int>, greater<int>>>::iterator iter; // 建立小组集合 for(int i = 0; i < n; i++) { if(ufs[i] < 0) { if(abs(ufs[i]) > 1) groups[i].push(nums[i]); } else groups[FindRoot(ufs, i)].push(nums[i]); } for(int i = 0; i < n; i++) { if(ufs[i] == -1) continue; int groupNo = FindRoot(ufs, i); nums[i] = groups[groupNo].top(); groups[groupNo].pop(); } return nums; } };复杂度分析
- 时间复杂度：排序数组的时间复杂度是构造的O(n)+排序的O(nlogn)，构造并查集的时间复杂度是O(nα(n))（路径压缩后的find和union操作的均摊时间复杂度为O(α(n))≈O(1)），priority_queue的插入和删除的时间复杂度是O(logn)，弹出堆顶元素的时间复杂度是O(1)的，并查集查找，所以建堆和构建答案的时间复杂度都是O(nlogn)的。——所以总的时间复杂度是O(nlogn)。
- 空间复杂度：因为不涉及很深的栈开销，所以空间复杂度即是主函数中定义的数据结构——O(n)。
官方题解
- 官解利用了并查集的思维但并没有实际构造一个并查集，而是将sortedNums排序后直接分别对每个小组调整位置，更巧妙了，这样既省了构造并查集的开销，也将堆的插入和删除这样的2次O(nlogn)操作转化为一次O(nlogn)加一次O(n)的赋值操作，规模上没变，但显然效率更高了，代价是需要额外的几个将近O(n)复杂度的辅助数组来做中间处理。复刻一下（稍微做了点优化）。
- ps.top1的大神方法过于高级，先不为难自己了。
class Solution { public: vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) { int n = nums.size(); vector<pair<int, int>> sortedNums(n); for(int i = 0; i < n; i++) { sortedNums[i] = {nums[i], i}; } // 让sortedNums升序排列 sort(sortedNums.begin(), sortedNums.end(), [](pair<int,int> a, pair<int,int> b) { if(a.first == b.first) return a.second < b.second; return a.first < b.first; }); int i = 0; while(i < n) { int start = i; // 以小组为单位单独处理 vector<int> groupValues, groupIndices; while(i < n && (i == start || sortedNums[i].first-sortedNums[i-1].first <= limit)) {// 注意这里没有用abs()，因为数组已经是非递减数组，不会小于0 groupValues.push_back(sortedNums[i].first); groupIndices.push_back(sortedNums[i].second); i++; } // 小组内的value已经是升序的了，只要把乱了的index重新排一下序，就能把对应的元素填到对应的index上了 sort(groupIndices.begin(), groupIndices.end()); for(int j = 0; j < groupIndices.size(); j++) { nums[groupIndices[j]] = groupValues[j]; } } return nums; } };- 时间复杂度：O(nlogn)。
- 空间复杂度：O(n)。
知识积累
- 并查集：是一种构建“相关”的小组的方法，将离散的小组成员分到一个小组中，通过路径压缩算法可以达到构建和查询的均摊时间复杂度达到O(α(n))的一种算法。
- priority_queue<type(数据类型), container(存数据的容器), fucntion(比较算法)>：堆，插入(push(num))和删除(pop())的时间复杂度都是O(logn)的，查询堆顶元素的时间复杂度是O(1)。
