LC.P1053[交换一次的先前排列]

题目描述

给你一个正整数数组 arr（可能存在重复的元素），请你返回可在 一次交换（交换两数字 arr[i] 和 arr[j] 的位置）后得到的、按字典序排列小于 arr 的最大排列。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^4

方法一：贪心

先从后往前遍历数组，找到第一个满足$arr[i - 1] > arr[i]$，此时$arr[i-1]$即为要交换的数字。

接着再从后往前遍历数组，找到第一个$arr[j] < arr[i - 1]且arr[j] \ne arr[j - 1]$的下标j，交换$arr[i - 1]$和$arr[j]$即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] prevPermOpt1(int[] arr) {
        int n = arr.length;
        for (int i = n - 1; i > 0; --i) {
            if (arr[i - 1] > arr[i]) {
                for (int j = n - 1; j > i - 1; --j) {
                    if (arr[j] < arr[i - 1] && arr[j] != arr[j - 1]) {
                        int temp = arr[i - 1];
                        arr[i - 1] = arr[j];
                        arr[j] = temp;
                        return arr;
                    }
                }
            }
        }
        return arr;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$