題目描述：

????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, do not allocate 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

分析：
????題意：給定一個整型數組，根據字典序，返回它的下一個排列（如果當前給出的是最后一個排列，返回第一個排列）。
????思路：這是一道經典的排列組合題，已經存在固定的算法去解決這個問題（Next lexicographical permutation algorithm）。
????假設數組為array，長度為n，步驟如下：
????① 首先找到最大的坐標i，使得array[i - 1] < array[i]。
????② 然后找到最大的坐標j，滿足j大于等于i，且array[j] > array[i - 1]。
????③ 交換array[j]和array[i - 1]的元素。
????④?將array[i]和array[n - 1]之間的元素反轉。
????時間復雜度為O(n)。
????如果有人直接調用C++庫函數next_permutation，我竟無言以懟。

代碼：

#include <bits/stdc++.h>using namespace std;/* // Accepted class Solution { public:void nextPermutation(vector<int>& nums) {next_permutation(nums.begin(), nums.end());} }; */class Solution { private: void reverse(vector<int>& vec, int start, int end){for(int i = start; i <= (start + end) / 2; i++){swap(vec[i], vec[start + end - i]);}}public:void nextPermutation(vector<int>& nums) {int n = nums.size();// Exceptional Case:if(n <= 1){return;}int i = n - 2;while(i >= 0 && nums[i] >= nums[i + 1]){i--;}if(i == -1){reverse(nums, 0, n - 1);return;}int j = i + 1;while(j <= n - 1 && nums[j] > nums[i]){j++;}// swapswap(nums[i], nums[j - 1]);reverse(nums, i + 1, n - 1);} };

總結

以上是生活随笔為你收集整理的LeetCode 31. Next Permutation（下一组排列）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。