LeetCode1053-交换一次的先前排列

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/previous-permutation-with-one-swap/

中文链接：https://leetcode-cn.com/problems/previous-permutation-with-one-swap/

题目详述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

题目详解

  • LeetCode31-下一个排列 是求下一个排列，而本题则求比当前排列小的最大排列。
  • 从后往前找到第一组位置，满足 A[i] > A[i + 1]（若找不到，说明是第一个排列，直接返回）。
  • 在 [i + 1, A.length - 1] 中找到小于 A[i] 最大的数，它的位置记为 k。
  • 交换 i、k 两处的值，得到的排列即为所求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_01053 {

    public int[] prevPermOpt1(int[] A) {
        for (int i = A.length - 2; i >= 0; --i) {
            if (A[i] > A[i + 1]) {
                int k = i + 1;
                for (int j = k + 1; j < A.length; ++j) {
                    if (A[j] < A[i] && A[j] > A[k]) {
                        k = j;
                    }
                }
                int t = A[i];
                A[i] = A[k];
                A[k] = t;
                return A;
            }
        }
        return A;
    }
}