C++算法： 最大化数组末位元素的最少操作次数

涉及知识点

数学

题目

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，这两个数组的长度都是 n 。

你可以执行一系列 操作（可能不执行）。

在每次操作中，你可以选择一个在范围 [0, n - 1] 内的下标 i ，并交换 nums1[i] 和 nums2[i] 的值。

你的任务是找到满足以下条件所需的 最小 操作次数：

nums1[n - 1] 等于 nums1 中所有元素的 最大值 ，即 nums1[n - 1] = max(nums1[0], nums1[1], …, nums1[n - 1]) 。

nums2[n - 1] 等于 nums2 中所有元素的 最大值 ，即 nums2[n - 1] = max(nums2[0], nums2[1], …, nums2[n - 1]) 。

以整数形式，表示并返回满足上述 全部 条件所需的 最小 操作次数，如果无法同时满足两个条件，则返回 -1 。

示例 1：

输入：nums1 = [1,2,7]，nums2 = [4,5,3]

输出：1

解释：在这个示例中，可以选择下标 i = 2 执行一次操作。

交换 nums1[2] 和 nums2[2] 的值，nums1 变为 [1,2,3] ，nums2 变为 [4,5,7] 。

同时满足两个条件。

可以证明，需要执行的最小操作次数为 1 。

因此，答案是 1 。

示例 2：

输入：nums1 = [2,3,4,5,9]，nums2 = [8,8,4,4,4]

输出：2

解释：在这个示例中，可以执行以下操作：

首先，选择下标 i = 4 执行操作。

交换 nums1[4] 和 nums2[4] 的值，nums1 变为 [2,3,4,5,4] ，nums2 变为 [8,8,4,4,9] 。

然后，选择下标 i = 3 执行操作。

交换 nums1[3] 和 nums2[3] 的值，nums1 变为 [2,3,4,4,4] ，nums2 变为 [8,8,4,5,9] 。

同时满足两个条件。

可以证明，需要执行的最小操作次数为 2 。

因此，答案是 2 。

示例 3：

输入：nums1 = [1,5,4]，nums2 = [2,5,3]

输出：-1

解释：在这个示例中，无法同时满足两个条件。

因此，答案是 -1 。

参数范围：

1 <= n == nums1.length == nums2.length <= 1000

1 <= nums1[i] <= 109

1 <= nums2[i] <= 109

分析

分两种情况：

Do函数

假定num1最后的元素小于nums2的元素。

错误解法

小元素上移，大元素下移。错误原因：有时不移动也符合条件，比如：{2,4},{1,5}，2和1无需移动。

代码

核心代码

class Solution {
public:
int minOperations(vector& nums1, vector& nums2) {
m_c = nums1.size();
const int iRet1 = min(Do(nums1, nums2), Do(nums2, nums1));
std::swap(nums1.back(), nums2.back());
const int iRet2 = min(Do(nums1, nums2), Do(nums2, nums1));
const int iRet = min(iRet1, iRet2 + 1);
return (m_c == iRet) ? -1 : iRet;
}
int Do(vector& nums1, vector& nums2)
{
int iRet = 0;
const int iMinMax = nums1.back();
const int iMaxMax = nums2.back();
if( iMinMax > iMaxMax )
{
return m_c;
}
for (int i = 0; i + 1 < m_c; i++)
{
const int iMin = min(nums1[i], nums2[i]);
const int iMax = max(nums1[i], nums2[i]);
if ((iMax > iMaxMax) || (iMin > iMinMax))
{
return m_c;
}
if (nums1[i] > iMinMax)
{
iRet++;
}
}
return iRet;
}
int m_c;
};

测试用例

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 num1, num2;
int res;
{
num1 = { 1 ,2, 7 };
num2 = { 4, 5, 3 };
res = Solution().minOperations(num1, num2);
Assert(1, res);
}
{
num1 = { 9, 14, 14 };
num2 = { 14, 11, 14 };
res = Solution().minOperations(num1, num2);
Assert(0, res);
}
}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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