[leetcode] Next Permutation
유의할점
순열의 끝
풀이
순열의 끝은 모든 수가 역순일 때이다. 예를 들면
1 2 5 4 3 에서 2 5 4 3은 2로 시작되는 순열의 끝이라고 할수있다.
2는 교체되어야 할것이다. 2보다 작은 수로 교체될수는없다. → 이전 permutation
즉 2의 바로 직후의 큰수를 구한뒤 교체한다. 교체된 수열의 처음은 오름차순 정렬이 될것이므로. 정렬한다. → 1 3 2 4 5
upper_bound를 위해서 정렬된 부분수열이 필요하므로 정렬후, upper_bound를 실행했다.
코드
C++
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int cur = nums.size();
while(cur--){
if(cur==0){
sort(nums.begin(),nums.end());
return;
}
int &beforeValue = nums[cur-1];
int ¤tValue = nums[cur];
if(beforeValue < currentValue){
sort(nums.begin()+cur,nums.end());
int changedIdx = upper_bound(nums.begin()+cur,nums.end(),nums[cur-1]) - nums.begin();
swap(nums[cur-1],nums[changedIdx]);
return;
}
}
}
};
Author And Source
이 문제에 관하여([leetcode] Next Permutation), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@6047198844/leetcode-Next-Permutation저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)