C++二分查找或并集查找：交换得到字典序最小的数组

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});
}

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;
};

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;
};