每日算法系列【LeetCode 1053】交换一次的先前排列

关注公众号【算法码上来】,每日算法干货马上就来!

题目描述

给你一个正整数的数组 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 <= A.length <= 10000
  • 1 <= A[i] <= 10000

题解

这题主要出发点有以下几点:

  • 首先要求交换后的字典序变小,那么一定要大的和小的交换,并且大的在前
  • 其次要求交换后的字典序尽量大,那么在满足第一点的情况下,大的元素要尽量靠后
  • 最后小的元素要尽量大,并且靠左

满足这几点条件,也就是要从最右边开始往左寻找,找到第一个上升的数字 A[i](从左往右看是下降,即 A[i] > A[i+1])。
这一点只为了保证上面的条件1,也就是 A[i] 右边存在比它小的元素。

然后在 A[i+1] 到 A[n-1] 之间所有比 A[i] 小的数字中找最大的那个就行了。如果最大的有多个相同的,取最左边的一个。

因为 A[i+1] 到 A[n-1] 子数组是单调递增的,所以不用全部遍历一遍,只需要从最右边开始往左找到第一个比 A[i] 小的数就行了。
然后从这个数开始,继续往左找和它相等的数,直到最左边一个相等的数 ,就是答案了。

代码

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        int n = A.size();
        for (int i = n-2; i >= 0; --i) {
            if (A[i] > A[i+1]) {
                for (int j = n-1; j > i; --j) {
                    if (A[j] < A[i]) {
                        for (int k = j; k >= i; --k) {
                            if (A[k] != A[j]) {
                                swap(A[i], A[k+1]);
                                break;
                            }
                        }
                        break;
                    }
                }
                break;
            }
        }
        return A;
    }
};

后记

最后不管是用时还是空间消耗都超越了100%的用户:
运行结果


   转载规则


《每日算法系列【LeetCode 1053】交换一次的先前排列》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
论文赏析【EMNLP19】语言模型效果不好?也许你可以给它添加一点句法信息 论文赏析【EMNLP19】语言模型效果不好?也许你可以给它添加一点句法信息
关注公众号【算法码上来】,每日算法干货马上就来! 论文地址PaLM: A Hybrid Parser and Language Model 介绍本文介绍了如何将一个句法分析器融入到神经网络语言模型中,这样在利用了句法信息增强语言模型效
2020-01-09
下一篇 
每日算法系列【LeetCode 315】计算右侧小于当前元素的个数 每日算法系列【LeetCode 315】计算右侧小于当前元素的个数
关注公众号【算法码上来】,每日算法干货马上就来! 题目描述给定一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素
2020-01-08
  目录