题解 | #换位#_牛客博客

题意整理

给定两个同样大小的数列，现在要将第一个变为严格降序，第二个变为严格升序。
可以交换两个数列同一列的元素，问最少交换多少次。
如果无法交换成严格有序，返回-1。

方法一（动态规划）

1.解题思路

状态定义： $dp[i][0]$ 表示当前无交换的最少交换次数， $dp[i][1]$ 表示当前有交换的最少交换次数。
状态初始化：当只有一个元素时，无交换的最少交换次数显然为0，有交换的最少交换次数显然为1。
状态转移：先将当前位置的状态设置为不可达，然后分四种情况进行讨论。如果 $firstRow[i]<firstRow[i-1]$ 并且 $secondRow[i]>secondRow[i-1]$ ，不需交换，用前一次无交换的最小次数跟新当前无交换的状态；如果 $firstRow[i]<secondRow[i-1]$ 并且 $secondRow[i]>firstRow[i-1]$ ，i-1处需要交换，用前一次有交换的最小次数跟新当前无交换的状态；如果 $secondRow[i]<firstRow[i-1]$ 并且 $firstRow[i]>secondRow[i-1]$ ，当前处需要交换，用前一次无交换的最小次数加1跟新当前有交换的状态；如果 $firstRow[i]>firstRow[i-1]$ 并且 $secondRow[i]<secondRow[i-1]$ ，i-1处和当前处都需要交换，用前一次有交换的最小次数加1跟新当前有交换的状态。
得到最后一个下标的两个状态值，取较小值即可。如果是不可达状态，返回-1，否则返回较小的状态值。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最小交换次数
     * @param firstRow int一维数组 第一行的数列数据
     * @param secondRow int一维数组 第二行的数列数据
     * @return int
     */
    //最大Integer型整数的一半
    final int INF=Integer.MAX_VALUE/2;

    public int arrange (int[] firstRow, int[] secondRow) {
        int n=firstRow.length;
        //dp[i][0]表示当前无交换的最少交换次数，dp[i][1]表示当前有交换的最少交换次数
        int[][] dp=new int[n][2];
        //初始化
        dp[0][0]=0;
        dp[0][1]=1;
        for(int i=1;i<n;i++){
            //设置为不可达状态
            dp[i][0]=INF;
            dp[i][1]=INF;
            //如果不需交换，跟新dp[i][0]
            if(firstRow[i]<firstRow[i-1]&&secondRow[i]>secondRow[i-1]){
                dp[i][0]=Math.min(dp[i][0],dp[i-1][0]);
            }
            //如果i-1处需要交换，跟新dp[i][0]
            if(firstRow[i]<secondRow[i-1]&&secondRow[i]>firstRow[i-1]){
                dp[i][0]=Math.min(dp[i][0],dp[i-1][1]);
            }
            //如果当前处需要交换，跟新dp[i][1]
            if(secondRow[i]<firstRow[i-1]&&firstRow[i]>secondRow[i-1]){
                dp[i][1]=Math.min(dp[i][1],dp[i-1][0]+1);
            }
            //如果i-1处和当前处都需要交换，跟新dp[i][1]
            if(firstRow[i]>firstRow[i-1]&&secondRow[i]<secondRow[i-1]){
                dp[i][1]=Math.min(dp[i][1],dp[i-1][1]+1);
            }
        }
        //取较小者
        int min=Math.min(dp[n-1][0],dp[n-1][1]);
        if(min==INF) return -1;
        return min;
    }
}

3.复杂度分析

时间复杂度：只需线性遍历数组一次，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外大小为 $n*2$ 的dp数组，所以空间复杂度为 $O(n)$ 。

方法二（空间优化）

1.解题思路

此方法和方法一的思路相同，分析可发现，每一次的状态值只与前一次的两个状态值有关，所以可能使用临时变量的方式先计算出跟新值，再用跟新值替换掉旧值，从而达到记录所有状态的目的。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最小交换次数
     * @param firstRow int一维数组 第一行的数列数据
     * @param secondRow int一维数组 第二行的数列数据
     * @return int
     */
    //最大Integer型整数的一半
    final int INF=Integer.MAX_VALUE/2;

    public int arrange (int[] firstRow, int[] secondRow) {
        int n=firstRow.length;
        //初始化
        int nochange=0;
        int change=1;
        for(int i=1;i<n;i++){
            //设置为不可达状态
            int tmp1=INF;
            int tmp2=INF;
            //如果不需交换，跟新dp[i][0]
            if(firstRow[i]<firstRow[i-1]&&secondRow[i]>secondRow[i-1]){
                tmp1=Math.min(tmp1,nochange);
            }
            //如果i-1处需要交换，跟新dp[i][0]
            if(firstRow[i]<secondRow[i-1]&&secondRow[i]>firstRow[i-1]){
                tmp1=Math.min(tmp1,change);
            }
            //如果当前处需要交换，跟新dp[i][1]
            if(secondRow[i]<firstRow[i-1]&&firstRow[i]>secondRow[i-1]){
                tmp2=Math.min(tmp2,nochange+1);
            }
            //如果i-1处和当前处都需要交换，跟新dp[i][1]
            if(firstRow[i]>firstRow[i-1]&&secondRow[i]<secondRow[i-1]){
                tmp2=Math.min(tmp2,change+1);
            }
            nochange=tmp1;
            change=tmp2;
        }
        //取较小者
        int min=Math.min(nochange,change);
        if(min==INF) return -1;
        return min;
    }
}

3.复杂度分析

时间复杂度：只需线性遍历数组一次，所以时间复杂度为 $O(n)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O(1)$ 。