C++ 中使数组严格递增

假设我们有两个数组 arr1 和 arr2，它们可以存储整数。我们必须找到使 arr1 严格递增所需的最小操作次数。在这里，我们可以选择两个索引 0 <= i < n 和 0 <= j < m 并执行赋值 arr1[i] = arr2[j]（n 和 m 分别是 arr1 和 arr2 的大小）

如果我们无法使数组 arr1 严格递增，则返回 -1。

因此，如果输入类似于 arr1 = [1,5,3,7,8]，arr2 = [1,3,2,5]，则输出将为 1，因为我们可以将 5 替换为 2，然后数组将为 [1,2,3,7,8]。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数 solve()，它将接收一个数组 arr1、一个数组 arr2、i、j、prev 和一个二维数组 dp，

• 如果 i >= arr1 的大小，则：

  • 返回 1

• j 为从 arr2[j] 及其上方的 arr2 的子数组的第一个元素

• 如果 dp[i, j] 不等于 -1，则：

  • 返回 dp[i, j]

• ret := arr2 的大小 + 1

• 如果 prev < arr1[i]，则：

  • ret := ret 和 solve(arr1, arr2, i + 1, j, arr1[i], dp) 的最小值

• 如果 j < arr2 的大小，则：

  • ret := ret 和 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp) 的最小值

• 返回 dp[i, j] = ret

• 从主方法中执行以下操作：

• 对数组 arr2 进行排序

• n := arr1 的大小

• m := arr2 的大小

• 定义一个大小为 2005 x 2005 的二维数组 dp 并将其填充为 -1

• ret := solve(arr1, arr2, 0, 0, -inf, dp)

• 返回（如果 ret > arr2 的大小，则返回 -1，否则返回 ret - 1）

让我们看看以下实现以更好地理解：

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, vector<vector<int> >& dp){
      if (i >= arr1.size())
         return 1;
      j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
      if (dp[i][j] != -1)
         return dp[i][j];
      int ret = arr2.size() + 1;
      if (prev < arr1[i]) {
         ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
      }
      if (j < arr2.size()) {
         ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
      }
      return dp[i][j] = ret;
   }
   int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2){
      sort(arr2.begin(), arr2.end());
      int n = arr1.size();
      int m = arr2.size();
      vector<vector<int> > dp(2005, vector<int>(2005, -1));
      int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
      return ret > arr2.size() ? -1 : ret - 1;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
   cout << (ob.makeArrayIncreasing(v,v1));
}

输入

{1,5,3,7,8}, {1,3,2,5}

输出

1

Arnab Chakraborty

更新于: 2020年6月4日

299 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习