首页 > 代码库 > LeetCode-Next Permutation-下一个排列-扫描+排序（不是最优解）
LeetCode-Next Permutation-下一个排列-扫描+排序（不是最优解）
https://oj.leetcode.com/problems/next-permutation/
我这个解法并不很好，是O(n^2)，这个在STL实现里应该是O(n)的。不过我的方法比较简单。
想法是首先需要找到一个left边界l，这个边界需要跟其后面的某个元素r交换使序列增大。然后在l前面的部分不变。后面的部分尽可能的小。
这个与l交换的r需要满足如下两个条件：
1)a[r]>a[l]，交换必须使得序列增大。
2)在[l+1,n)里，满足a[i]>a[l]的所有i里面a[r]应该是最小的。
在这样交换后，对[l+1,n)进行一次排序，使其序列最小。即可。
const int INF=9999;class Solution {public: int n,m; void nextPermutation(vector<int> &num) { n=num.size(); if (n<2) return; int l,r; for (l=n-2;l>=0;l--){ int rv=INF; r=-1; for (int i=l+1;i<n;i++){ if (num[i]>num[l] && num[i]<=rv){ rv=num[i]; r=i; } } if (r!=-1) { break; } } if (r!=-1) { swap(num[l],num[r]); sort(num.begin()+l+1,num.end()); } else sort(num.begin(),num.end()); }};
LeetCode-Next Permutation-下一个排列-扫描+排序（不是最优解）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。