题目
给你一个整数数组 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
