? ? ? ? leetcode原題鏈接：下一個排列

題目描述

? ? ? 整數數組的一個?排列? 就是將其所有成員以序列或線性順序排列。

• 例如，arr = [1,2,3]?，以下這些都可以視作?arr?的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]?。
• 整數數組的?下一個排列?是指其整數的下一個字典序更大的排列。更正式地，如果數組的所有排列根據其字典順序從小到大排列在一個容器中，那么數組的?下一個排列?就是在這個有序容器中排在它后面的那個排列。如果不存在下一個更大的排列，那么這個數組必須重排為字典序最小的排列（即，其元素按升序排列）。
• 例如，arr = [1,2,3]?的下一個排列是?[1,3,2]?。
• 類似地，arr = [2,3,1]?的下一個排列是?[3,1,2]?。
• 而?arr = [3,2,1]?的下一個排列是?[1,2,3]?，因為?[3,2,1]?不存在一個字典序更大的排列。

? ? ? 給你一個整數數組?nums?，找出?nums?的下一個排列。

? ? ? 必須?原地?修改，只允許使用額外常數空間。

示例 1：

輸入：nums = [1,2,3]
輸出：[1,3,2]

示例 2：

輸入：nums = [3,2,1]
輸出：[1,2,3]

示例 3：

輸入：nums = [1,1,5]
輸出：[1,5,1]

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

解題方法：

? ? 1. 從右邊向左，尋找第一個降序的數字j，對應的波峰為i （j=i-1)。

? ? 2.?再從右向左，找到第一個比j大的元素位置k(這個k必然存在,因為nums[j]>nums[i])。

? ? 3.?交換nums[j]和nums[k]。

? ? 4.?對[j+1, n-1]區間的元素從小到大排序，此時只需要反轉下數字即可reverse。

C++代碼

#include <iostream>
#include <vector>
#include <algorithm> // std::reverse()class Solution {
public:void nextPermutation(std::vector<int>& nums) {int n = nums.size();if (n == 0) {return;}// 1.從右邊向左，尋找第一個將序的數字j，對應的波峰為iint i = n - 1; //從右向左尋找第一個波峰的位置while (i > 0 && nums[i] <= nums[i - 1]) { //比較num[i]和num[i-1]的值,所以這里i--;}if (i == 0) { //i到了最左邊,說nums[0]是最大值,此時沒有更大的值,則返回最小值(因為數組本身已經是最大值)std::reverse(nums.begin(), nums.end());return;}int j = i - 1; //j指向第一個波峰左邊的位置// 2.再從右向左，找到第一個比j大的元素位置k(這個k必然存在,因為nums[j]>nums[i])int k = n - 1;while (k >= i && nums[k] <= nums[j]) {k--;}// 3. 交換nums[j]和nums[k]std::swap(nums[j], nums[k]);// 4. 對[j+1, n-1]區間的元素從小到大排序，此時只需要反轉下數字即可reversestd::reverse(nums.begin() + j + 1, nums.end());}
};