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

分析

分两种情况：


一	nums1.back()和nums2.back()交换
二	nums1.back()和nums2.back()不交换

Do函数

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


nums1[i[和nums2[i]都小于等于最后元素	iRet不变
nums1[i[和nums2[i]j交换后， nums1[i[和nums2[i]都小于等于最后元素	iRet++
交换后，也无法满足要求	return m_c

错误解法

小元素上移，大元素下移。错误原因：有时不移动也符合条件，比如：{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);
 }
 }

洒家想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
墨家名称的来源：有所得以墨记之。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者操作系统：win10 开发环境： VS2022 C++17

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