題目
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement. Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]
Example 2:
Input: nums = [1,1,5]
Output: [1,5,1]
解題方法
從右向左尋找遞減序列的轉折點： 找到第一個位置 i，使得 nums[i] < nums[i + 1]。這表示從 i 之後的數字是遞減的。
如果找不到，說明當前排列是最大的，直接反轉陣列： 如果整個陣列是遞減的（如 [3, 2, 1]），則直接反轉整個陣列變為最小排列（如 [1, 2, 3]）。
找到比 nums[i] 大的最小數字並交換： 在 i 右邊的數字中，找到最接近且比 nums[i] 大的數字 nums[j]，然後交換 nums[i] 和 nums[j]。
反轉 i + 1 之後的子陣列： 這樣能保證轉折點後的數字變為最小排列，確保整體是下一個排列。
程式
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int size = nums.size();
cout << size ;
}
};
int main(){
Solution sol;
cout << sol.divide(-2147483648, 3) << endl;
return 0;
}
Photo by Pawel Czerwinski on Unsplash