JAVA程序设计（使数组严格递增（LeetCode：1187））
给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。
每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。
【JAVA程序设计（使数组严格递增（LeetCode：1187））】如果无法让 arr1 严格递增，请返回 -1。
示例 1：
输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。
示例 2：
输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]
输出：2
解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。
示例 3：
输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出：-1
解释：无法使 arr1 严格递增。
提示：
1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9
思路：定义dp[i][j]，表示前i个数替换j次后的最后一位的最小值。复杂度O(n^2logm)
class Solution {final static int inf = Integer.MAX_VALUE;
public int makeArrayIncreasing(int[] arr1, int[] arr2) {int n = arr1.length;
int m = arr2.length;
int[][] dp = new int[n + 1][n + 1];
for (int i = 0;
i <= n;
i++)
Arrays.fill(dp[i], inf);
Arrays.sort(arr2);
dp[0][0] = -1;
for (int i = 1;
i <= n;
i++) {
for (int j = 0;
j <= i;
j++) {
if (arr1[i - 1] > dp[i - 1][j])
dp[i][j] = arr1[i - 1];
if (j > 0) {
int p = find(arr2, dp[i - 1][j - 1]);
if (p < m) dp[i][j] = Math.min(dp[i][j], arr2[p]);
}
}
}for (int j = 0;
j <= n;
j++)
if (dp[n][j] != inf)
return j;
return -1;
}private int find(int[] arr, int val) {int l = 0, r = arr.length;
while (l < r) {
int mid = (l + r) / 2;
if (arr[mid] > val)
r = mid;
else
l = mid + 1;
}return r;
}
}推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 由浅入深理解AOP
- 【译】20个更有效地使用谷歌搜索的技巧
- mybatisplus如何在xml的连表查询中使用queryWrapper
- MybatisPlus|MybatisPlus LambdaQueryWrapper使用int默认值的坑及解决
- MybatisPlus使用queryWrapper如何实现复杂查询
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- iOS中的Block