C++LeetCode 구현(31.다음 배열)

[LeetCode]31.Next Permutation 다음 줄
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
이 문 제 는 다음 배열 순 서 를 구 합 니 다.문제 에서 준 예 를 통 해 알 수 있 습 니 다.주어진 배열 이 내림차 순 이 라면 전체 배열 의 마지막 상황 임 을 설명 합 니 다.다음 배열 은 초기 상황 이 므 로 이전 블 로 그 를 참조 할 수 있 습 니 다.  Permutations 。다음 예 를 들 어 다음 과 같은 배열 이 있 습 니 다.
1　　2　　7　　4　　3　　1
다음 배열 은:
1　　3　　1　　2　　4　　7
그렇다면 어떻게 얻 었 을 까?우 리 는 원수 조 를 관찰 한 결과 끝 에서 앞 을 보면 숫자 가 점점 커지 고 2 가 되 어서 야 줄 어 든 것 을 발견 할 수 있다.그리고 뒤에서 2 보다 큰 첫 번 째 숫자 를 찾 으 면 3 이다.그러면 우 리 는 2 와 3 을 교환 하고 이때 3 뒤에 있 는 숫자 를 바 꾸 면 된다.절 차 는 다음 과 같다.
1　　2　　7　　4　　3　　1
1　　2　　7　　4　　3　　1
1　　3　　7　　4　　2　　1
1　　3　　1　　2　　4　　7
해법 1:

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        int i, j, n = num.size();
        for (i = n - 2; i >= 0; --i) {
            if (num[i + 1] > num[i]) {
                for (j = n - 1; j > i; --j) {
                    if (num[j] > num[i]) break;
                }
                swap(num[i], num[j]);
                reverse(num.begin() + i + 1, num.end());
                return;
            }
        }
        reverse(num.begin(), num.end());
    }
};

아래 의 이런 문법 은 좀 더 간결 하지만 전체적인 사고방식 과 위의 해법 은 별 차이 가 없다.코드 는 다음 과 같다.
해법 2:

class Solution {
public:
    void nextPermutation(vector<int>& nums) {int n = nums.size(), i = n - 2, j = n - 1;
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;
        if (i >= 0) {
            while (nums[j] <= nums[i]) --j;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

C++구현 LeetCode(31.다음 배열)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 다음 배열 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!