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

有两个具有相同非零长度的整数序列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