本文涉及的基础知识点
题目
给你一个下标从 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 <= 105
1 <= nums[i] <= 109
1 <= limit <= 109
分析
时间复杂度
O(nlogn)，枚举每个元素，每个枚举都需要二分查找。
代码
分析
setValue是nums按降序排序，如果一个数x1能替换比它大的数，那么一定存在一个比它大的数x2，且x2-x1 <= limit。setNot记录所有不存在x2的x1。
求一个数x能不替换成的最小数y：
在setValue中，y在x的右边。
setNot中 y在setNot.upper_bound(n)的左边
核心代码
class Solution { public: vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) { std::multiset<int,std::greater<>> setValue(nums.begin(), nums.end()); std::set<int, std::greater<>> setNot; for ( auto it = setValue.begin(); it != setValue.end(); ++it ) { auto itNext = std::next(it); if ((setValue.end() != itNext) && (*it - *itNext > limit)) { setNot.emplace(*itNext); } } for ( auto& n : nums) { auto it = setNot.upper_bound(n); int iEnd = (setNot.end() == it) ? -1 : *it; auto it2 = setValue.lower_bound(iEnd); if( setValue.begin() != it2 ) { n = *std::prev(it2); setValue.erase(setValue.find(n)); continue; } setValue.erase(setValue.find(n)); auto ij = setValue.lower_bound(n); if ((setValue.end() != ij) && (setValue.begin() != ij)) { if (*std::prev(ij) - *ij > limit) { setNot.emplace(*ij); } } } return nums; } };
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector nums, res; int limit; { nums = { 1, 5, 3, 9, 8 }; limit = 2; Solution slu; res = slu.lexicographicallySmallestArray(nums, limit); Assert(res, vector{1, 3, 5, 8, 9}); } { nums = { 1, 7, 6, 18, 2, 1 }; limit = 3; Solution slu; res = slu.lexicographicallySmallestArray(nums, limit); Assert(res, vector{1, 6, 7, 18, 1, 2}); } { nums = { 1, 7, 28, 19, 10 }; limit = 3; Solution slu; res = slu.lexicographicallySmallestArray(nums, limit); Assert(res, vector{1, 7, 28, 19, 10}); }
//CConsole::Out(res);
}
并集查找
周赛时，没想到并集查找，用自己想的办法，每个细节都需要斟酌、尝试，非常花时间。建议尽量用现有算法。
分析
规则一：如果a,b能交换，b,c能交换，则a,b,c可以交换。
| a b c |
| b a c |
| c a b |
| c b a |
规则二：如果a b c能互换，c d 能互换，则a 和d 能互换。
| a b c d |
| **c b a ** d |
| d b a c |
| d b c a |
规则一，a b ,b c => 可以调整成任何顺序
规则二： a b,b c ,c d=>可以调整成任何顺序
规则三：增加a e可以互换
| a ？？？ e |
| e ??? a |
| 根据规则二，???a 可以换成任意顺序 |
总结
利用图论知识，a b能互换则a b连通，利用并集查找解决问题。同一个并集查找升序排序。
代码
class CUnionFind { public: CUnionFind(int iSize) :m_vNodeToRegion(iSize) { for (int i = 0; i < iSize; i++) { m_vNodeToRegion[i] = i; } m_iConnetRegionCount = iSize; } int GetConnectRegionIndex(int iNode) { int& iConnectNO = m_vNodeToRegion[iNode]; if (iNode == iConnectNO) { return iNode; } return iConnectNO = GetConnectRegionIndex(iConnectNO); } void Union(int iNode1, int iNode2) { const int iConnectNO1 = GetConnectRegionIndex(iNode1); const int iConnectNO2 = GetConnectRegionIndex(iNode2); if (iConnectNO1 == iConnectNO2) { return; } m_iConnetRegionCount–; if (iConnectNO1 > iConnectNO2) { UnionConnect(iConnectNO1, iConnectNO2); } else { UnionConnect(iConnectNO2, iConnectNO1); } } bool IsConnect(int iNode1, int iNode2) { return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2); } int GetConnetRegionCount()const { return m_iConnetRegionCount; } vector GetNodeCountOfRegion()//各联通区域的节点数量 { const int iNodeSize = m_vNodeToRegion.size(); vector vRet(iNodeSize); for (int i = 0; i < iNodeSize; i++) { vRet[GetConnectRegionIndex(i)]++; } return vRet; } std::unordered_map<int, vector> GetNodeOfRegion() { std::unordered_map<int, vector> ret; const int iNodeSize = m_vNodeToRegion.size(); for (int i = 0; i < iNodeSize; i++) { ret[GetConnectRegionIndex(i)].emplace_back(i); } return ret; } private: void UnionConnect(int iFrom, int iTo) { m_vNodeToRegion[iFrom] = iTo; } vector m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引 int m_iConnetRegionCount; }; class Solution { public: vector lexicographicallySmallestArray(vector& nums, int limit) { m_c = nums.size(); auto vSort = nums; sort(vSort.begin(), vSort.end()); CUnionFind uf(m_c); for (int i = m_c - 1; i > 0; i–) { if (vSort[i] - vSort[i - 1] <= limit) { uf.Union(i, i - 1); } } unordered_map<int, int> mValueToRegion; unordered_map<int, vector> mReginToValues; for (int i = 0; i < m_c; i++) { const int iRegion = uf.GetConnectRegionIndex(i); mValueToRegion[vSort[i]] = iRegion; mReginToValues[iRegion].emplace_back(vSort[i]); } for ( auto& [region, v] : mReginToValues) { std::sort(v.begin(), v.end(), std::greater<>()); } for (int i = 0; i < m_c; i++) { const int iRegion = mValueToRegion[nums[i]]; nums[i] = mReginToValues[iRegion].back(); mReginToValues[iRegion].pop_back(); } return nums; } int m_c; };
/
优化
各连通区域是连续的，所以直接处理更简单。mValueToRegion[i] 记录第i个连通区域的数。比如：limit是4
14 12 8 3 1 ，可以分成{14 12 8} {3 1}.
代码
class Solution { public: vector lexicographicallySmallestArray(vector& nums, int limit) { m_c = nums.size(); auto vSort = nums; sort(vSort.begin(), vSort.end()); vector<vector> vGroupNum; unordered_map<int, int> mValueToRegion; for (int i = 0 ; i < m_c ; i++ ) { if ((0 == i) || (vSort[i] - vSort[i - 1] > limit)) { vGroupNum.emplace_back(); } vGroupNum.back().emplace_back(vSort[i]); mValueToRegion[vSort[i]] = vGroupNum.size() - 1; } for (auto& v : vGroupNum) { std::sort(v.begin(), v.end(), std::greater<>()); } for (int i = 0; i < m_c; i++) { const int iRegion = mValueToRegion[nums[i]]; nums[i] = vGroupNum[iRegion].back(); vGroupNum[iRegion].pop_back(); } return nums; } int m_c; };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
