LEETCODE 1053. Previous Permutation With One Swap 解题思路分析

题目大意：

交换一次的先前排列

给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。

如果无法这么操作，就请返回原数组。

示例 1：

输入：[3,2,1]
输出：[3,1,2]
解释：
交换 2 和 1

示例 2：

输入：[1,1,5]
输出：[1,1,5]
解释： 
这已经是最小排列

示例 3：

输入：[1,9,4,6,7]
输出：[1,7,4,6,9]
解释：
交换 9 和 7

示例 4：

输入：[3,1,1,3]
输出：[1,3,1,3]
解释：
交换 1 和 3

提示：

1. 1 <= A.length <= 10000
2. 1 <= A[i] <= 10000

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1053

解题思路分析：

题目要求求出交换任意两位后，按字典序排列小于 A 的最大可能排列。由于都是数字，并且交换后的排列长度不变，因此我们可以理解为，数字小于A 的最大可能排列。

暴力解法是将所有位置都交换一次，找到一个小于原数的最大值。这样做估计会超时（没验证），我们还是直接说下最优方案。

本题会用到一些贪心思想。对于任意一个数字，如果想变为小于当前的值，我们可以将数字的任意一位变小，不过考虑到求变小后的最大值，就应该想到减小低位上的数字要比减小高位数字要更划算（减少的越少，改变后的数字就越接近原数字，也就相对较大）。再者，对于同一位上的数字，肯定也是减小的越少越好。能减小到多少这要取决于当前位之后的低位上小于当前数并且最大的数字是多少。这样问题就转化为：从数组A的最后一位向前循环，找到一个低于当前位，并且比当前位小的数中的最大值。找到后，交换两数的位置即是答案。

再解释一下，为什么要找比当前位低的数中小于当前值的最大值呢？对于低位来说，当前位是高位，两位交换后，高位数变小，低位数变大，这样才能保证整体数值变小，且该值最大。

完整代码：

public int[] prevPermOpt1(int[] A) {
    for(int i = A.length-1;i>=0;i--){ // 从最后一位向前循环数组
        int max = -1; // 定义最大数
        int maxIndex = i; // 定义最大值相对应的下标
        for(int j=i+1;j<A.length;j++){ // 从当前位向后循环，找到小于当前位的最大数
            if(A[j] < A[i] && A[j] > max){
                max = A[j];
                maxIndex = j;
            }
        }
        if(max != -1){ // 如果找到最大数，交换最大数于当前数两位的值，返回结果。
            A[maxIndex] = A[maxIndex]^A[i];
            A[i] = A[maxIndex]^A[i];
            A[maxIndex] = A[maxIndex]^A[i];
            break;
        }
    }
    return A;
}

本题解法运行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Previous Permutation With One Swap.

Memory Usage: 40.7 MB, less than 100.00% of Java online submissions for Previous Permutation With One Swap.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1053-previous-permutation-with-one-swap-解题思路分析/