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(vectorint 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(vectorint 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; } vectorint lexicographicallySmallestArray(vectorint nums, int limit) { // 目标是得到字典序最小的数组即最小的数也就是尽可能让更小值放在更前面 int n nums.size(); vectorint ufs(n, -1); for(int i 0; i n; i) { for(int j i1; j n; j) { if(abs(nums[i]-nums[j]) limit) { Union(ufs, i, j); } } } unordered_mapint, priority_queueint, vectorint, greaterint groups; unordered_mapint, priority_queueint, vectorint, greaterint::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))的复杂度构造并查集了。所以不妨构造一个形如pairvalue, index的数组然后对根据valueindex进行排序这样我们就可以得到一个按value升序同value按index升序的数组。再基于这个数组遍历构造并查集剩下的部分沿用原来的方案即可。只能说太巧妙了这题中等难度感觉屈才了感觉蛮考验数据结构的设计的相比于算法上困难的题目这个题目感觉更考验巧思或者工程能力。代码实现class Solution { public: int FindRoot(vectorint 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(vectorint 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; } vectorint lexicographicallySmallestArray(vectorint nums, int limit) { // 目标是得到字典序最小的数组即最小的数也就是尽可能让更小值放在更前面 int n nums.size(); vectorint ufs(n, -1); vectorpairint, int sortedNums(n); for(int i 0; i n; i) { sortedNums[i] make_pair(nums[i], i); } sort(sortedNums.begin(), sortedNums.end(), [](pairint,int a, pairint,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_mapint, priority_queueint, vectorint, greaterint groups; unordered_mapint, priority_queueint, vectorint, greaterint::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: vectorint lexicographicallySmallestArray(vectorint nums, int limit) { int n nums.size(); vectorpairint, int sortedNums(n); for(int i 0; i n; i) { sortedNums[i] {nums[i], i}; } // 让sortedNums升序排列 sort(sortedNums.begin(), sortedNums.end(), [](pairint,int a, pairint,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; // 以小组为单位单独处理 vectorint 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_queuetype(数据类型), container(存数据的容器), fucntion(比较算法)堆插入(push(num))和删除(pop())的时间复杂度都是O(logn)的查询堆顶元素的时间复杂度是O(1)。 每日leetcode（这题真的很有意思，第一次搞半天搞错瓶颈在哪）
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(vectorint 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(vectorint 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; } vectorint lexicographicallySmallestArray(vectorint nums, int limit) { // 目标是得到字典序最小的数组即最小的数也就是尽可能让更小值放在更前面 int n nums.size(); vectorint ufs(n, -1); for(int i 0; i n; i) { for(int j i1; j n; j) { if(abs(nums[i]-nums[j]) limit) { Union(ufs, i, j); } } } unordered_mapint, priority_queueint, vectorint, greaterint groups; unordered_mapint, priority_queueint, vectorint, greaterint::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))的复杂度构造并查集了。所以不妨构造一个形如pairvalue, index的数组然后对根据valueindex进行排序这样我们就可以得到一个按value升序同value按index升序的数组。再基于这个数组遍历构造并查集剩下的部分沿用原来的方案即可。只能说太巧妙了这题中等难度感觉屈才了感觉蛮考验数据结构的设计的相比于算法上困难的题目这个题目感觉更考验巧思或者工程能力。代码实现class Solution { public: int FindRoot(vectorint 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(vectorint 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; } vectorint lexicographicallySmallestArray(vectorint nums, int limit) { // 目标是得到字典序最小的数组即最小的数也就是尽可能让更小值放在更前面 int n nums.size(); vectorint ufs(n, -1); vectorpairint, int sortedNums(n); for(int i 0; i n; i) { sortedNums[i] make_pair(nums[i], i); } sort(sortedNums.begin(), sortedNums.end(), [](pairint,int a, pairint,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_mapint, priority_queueint, vectorint, greaterint groups; unordered_mapint, priority_queueint, vectorint, greaterint::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: vectorint lexicographicallySmallestArray(vectorint nums, int limit) { int n nums.size(); vectorpairint, int sortedNums(n); for(int i 0; i n; i) { sortedNums[i] {nums[i], i}; } // 让sortedNums升序排列 sort(sortedNums.begin(), sortedNums.end(), [](pairint,int a, pairint,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; // 以小组为单位单独处理 vectorint 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_queuetype(数据类型), container(存数据的容器), fucntion(比较算法)堆插入(push(num))和删除(pop())的时间复杂度都是O(logn)的查询堆顶元素的时间复杂度是O(1)。