2948. 通过交换元素构造字典序最小数组
💡
原文英文，约1200词，阅读约需5分钟。
📝
内容提要
给定一个正整数数组和限制值，通过构建虚拟图识别连接组件并排序，可以得到字典序最小的数组。
🎯
关键要点
- 给定一个正整数数组和限制值，通过构建虚拟图识别连接组件并排序，可以得到字典序最小的数组。
- 数组 a 在字典序上小于数组 b，当且仅当在第一个不同的索引处，a[i] < b[i]。
- 交换条件：只有当两个元素的差值小于或等于限制值时，才能进行交换。
- 使用并查集（DSU）或排序技术，可以有效地将可以交换的元素分组。
- 对于每个组，排序索引和值，以实现最小的字典序。
- 构建组：将数组视为虚拟图，合法交换定义边，使用排序或并查集高效分组。
- 输出构造：将排序后的值放回其原始位置，返回修改后的数组。
- 时间复杂度：排序的时间复杂度为 O(n log n)，线性遍历的时间复杂度为 O(n)，整体时间复杂度为 O(n log n)。
➡️
