[二分查找]LeetCode2009 :使数组连续的最少操作数-阿里云开发者社区

[二分查找]LeetCode2009 :使数组连续的最少操作数

2024-01-22 42

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： [二分查找]LeetCode2009 :使数组连续的最少操作数

题目

给你一个整数数组 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;
}
};