[二分查找]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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛