本文涉及的基础知识点
二分查找算法合集
LeetCode2948交换得到字典序最小的数组
给你一个下标从 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;
};
