使序列递增的最小交换次数

有两个具有相同非零长度的整数序列A和B。可以交换它们的一些元素A[i]和B[i]。 注意，两个可交换的元素在它们各自的序列中处于相同的索引位置。进行一些交换之后，A和B需要严格递增。 （当且仅当A[0] < A[1] < A[2] < ... < A[A.length - 1]时，序列严格递增。）

给定A和B，返回使两个序列严格递增的最小交换次数。 保证给定的输入经过交换可以满足递增的条件。

minimum-swaps-to-make-sequences-increasing

样例

样例 1:

输入: A = [1,3,5,4], B = [1,2,3,7] 输出: 1 解释: 交换A[3] and B[3]. 两个序列变为: A = [1,3,5,7] 和 B = [1,2,3,4], 此时它们都是严格递增的。

样例 2:

输入: A = [2,4,5,7,10], B = [1,3,4,5,9] 输出: 0 题目是保证有解的 思路1、使用动态规划 index 0 1 2 3 4 A 1 3 5 4 9 B 1 2 3 7 10 dp[index][0] 0 0 0 2 1 dp[index][1] 1 1 2 1 2 思路2 跟思路1 差不多 index 0 1 2 3 4 A 1 3 5 4 9 B 1 2 3 7 10 swapRecord 1 1 2 1 2 fixRecord 0 0 0 2 1 记录 swapRecord fixRecord的值 具体代码试下如下 public class Solution { /** * @param a: an array * @param b: an array * @return: the minimum number of swaps to make both sequences strictly increasing */ public int minSwap(int[] a, int[] b) { // Write your code here if(a.length == 0){ return 0; } int[][] dp = new int[a.length][2]; dp[0][0] = 0; dp[0][1] = 1; for (int i = 1; i < dp.length; i++) { if (a[i - 1] >= b[i] || b[i - 1] >= a[i]) { dp[i][0] = dp[i - 1][0]; dp[i][1] = dp[i - 1][1] + 1; } else if (a[i - 1] >= a[i] || b[i - 1] >= b[i]) { dp[i][1] = dp[i - 1][0] + 1; dp[i][0] = dp[i - 1][1]; } else { int min = Math.min(dp[i - 1][0], dp[i - 1][1]); dp[i][0] = min; dp[i][1] = min + 1; } } return Math.min(dp[dp.length - 1][0], dp[dp.length - 1][1]); } } public class Solution { public int minSwap(int[] a, int[] b) { int swapRecord = 1; int fixRecord = 0; for (int i = 1; i < a.length; i++) { if (a[i - 1] >= b[i] || b[i - 1] >= a[i]) { swapRecord++; } else if (a[i - 1] >= a[i] || b[i - 1] >= b[i]) { int temp = swapRecord; swapRecord = fixRecord + 1; fixRecord = temp; } else { int min = Math.min(swapRecord, fixRecord); swapRecord = min + 1; fixRecord = min; } } return Math.min(swapRecord, fixRecord); } }

源码地址 ：https://github.com/xingfu0809/Java-LintCode