How does C++ achieve the next arrangement?
This article mainly introduces "how C++ achieves the next arrangement". In daily operation, I believe many people have doubts about how C++ can achieve the next arrangement. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the questions of "how C++ can achieve the next arrangement"! Next, please follow the editor to study!
Next Permutation 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
This question allows us to find the next sort order, as can be seen from the example given in the title. If a given array is in descending order, it means that it is the last case of full permutation, then the next permutation is the most initial case, which can be seen in the previous blog Permutations. Let's take a look at the following example, which has the following array
1 2 7 4 3 1
The next arrangement is:
1 3 1 2 4 7
So how did you get it? by observing the original array, we can find that if you look at the end and forward, the number gradually increases, and then it decreases at 2: 00, and then you look for the first number larger than 2 from back to front, which is 3. Then we exchange 2 and 3, and then transpose all the numbers after 3. The steps are as follows:
1 2 7 4 3 1
1 2 7 4 3 1
1 3 7 4 2 1
1 3 1 2 4 7
Solution 1:
Class Solution {public: void nextPermutation (vector & 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 ());}}
The following way of writing is more concise, but the overall idea is no different from the above solution, see the code below:
Solution 2:
Class Solution {public: void nextPermutation (vector& 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])
