本文主要是介绍[二分查找]LeetCode2009 :使数组连续的最少操作数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文涉及的基础知识点
二分查找算法合集
作者推荐
动态规划LeetCode2552：优化了6版的1324模式
题目
给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。
如果 nums 满足以下条件，那么它是 连续的 ：
nums 中所有元素都是 互不相同 的。
nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。
比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。
请你返回使 nums 连续 的 最少 操作次数。
示例 1：
输入：nums = [4,2,5,3]
输出：0
解释：nums 已经是连续的了。
示例 2：
输入：nums = [1,2,3,5,6]
输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。
示例 3：
输入：nums = [1,10,100,1000]
输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109
分析
时间复杂度
O(nlogn)。
分析
如果所有元素都改变，则改变次数为n。
如果有元素没改变，则枚举没改变元素中的最小值，假定没改变元素的最小值为x，则新数组的范围为[x,x+n)。下面来证明：
假定新数组为[y,y+n)。则y <=x，否则和x是最小值矛盾。[y,x)全部需要改变，所以[y,x)换[y+n,x+n)结果不会变坏。
步骤
将nums排序，除重复。
枚举nums[i]，统计[nums[i],nums[i]+n)的数量，这些数不需要改变。
代码
核心代码
class Solution {
public:int minOperations(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());nums.erase(std::unique(nums.begin(), nums.end()), nums.end());int iRet = n;for (int i = 0; i < nums.size(); i++){auto it = std::lower_bound(nums.begin() + i, nums.end(), nums[i] + n);iRet = min(iRet, n - (it - nums.begin() - i));}return iRet;}
};
测试用例
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]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector nums;
int res;
{
nums = { 4, 2, 5, 3 };
Solution slu;
auto res = slu.minOperations(nums);
Assert(0, res);
}
{
nums = { 1,2,3,5,6 };
Solution slu;
auto res = slu.minOperations(nums);
Assert(1, res);
}
{
nums = { 1,10,100,1000 };
Solution slu;
auto res = slu.minOperations(nums);
Assert(3, res);
}
{
nums = { 1,1 };
Solution slu;
auto res = slu.minOperations(nums);
Assert(1, res);
}
//CConsole::Out(res);
}
2023年3月版：树状树状
template
class CTreeArr
{
public:
CTreeArr(int iSize) :m_vData(iSize+1)
{
}
void Add(int index, T value)
{
index++;
while (index < m_vData.size())
{
m_vData[index] += value;
index += index&(-index);
}
}
T Sum(int index)
{
index++;
T ret = 0;
while (index )
{
ret += m_vData[index];
index -= index&(-index);
}
return ret;
}
private:
vector m_vData;
};
class Solution {
public:
int minOperations(vector& nums) {
const int iOldSize = nums.size();
std::sort(nums.begin(), nums.end());
nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
CTreeArr tree(nums.size());
int iMax = 0; //记录不需要改变的数量
for (int i = 0; i < nums.size(); i++)
{//nums[i]是最后一个没有改变的数
tree.Add(i, 1);
int iCurMax = tree.Sum(i);
auto iLessNum = std::lower_bound(nums.begin(), nums.end(), nums[i] - iOldSize + 1) - nums.begin();
if (iLessNum > 0 )
{
iCurMax -= tree.Sum(iLessNum - 1);
}
iMax = max(iMax, iCurMax);
}
return iOldSize - iMax;
}
};
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
这篇关于[二分查找]LeetCode2009 :使数组连续的最少操作数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
