Keshawn_lu's Blog

Leetcode 1053. 交换一次的先前排列

数组
字数统计: 415阅读时长: 1 min
2023/04/03 Share

题目简介：

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

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

示例 1：

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

示例 2：

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

示例 3：

1
2
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 的最大排列，所以交换的位置越往后越好，所以我们从前往后遍历，找到最后一个arr[i] < arr[i - 1]的位置i - 1作为需要交换的位置pos1。

另外一个位置则往后遍历，找到小于arr[pos1]并且和arr[pos1]差值最小的arr[i]，作为pos2。

交换这两个位置即可。

tip:

  • 当往后遍历遇到arr[i + 1] == arr[i]的情况时，直接continue，因为两个值相等时，交换的位置越靠前则交换后的数组越大。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {

        int pos1 = -1;
        int pos2 = -1;

        for(int i = 1; i < arr.size(); i++){

            if(arr[i] < arr[i - 1]){

                pos1 = i - 1;
                pos2 = i;

                while(i + 1 < arr.size() && arr[i + 1] >= arr[i]){

                    if(arr[i + 1] >= arr[pos1] || arr[i + 1] == arr[i]){

                        i++;
                        continue;
                    }

                    pos2 = i + 1;
                    i++;
                }
            }
        }

        if(pos1 != -1)
            swap(arr[pos1], arr[pos2]);

        return arr;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网