README
¶
Next Permutation
所谓下一个排列就是当前数字列表中数字组成的列表中比当前列表大的最小的列表。
为了得到这样的列表，分析如下：
- 下一个数比当前数大，那么只需要将当前数中的一个比较小的数替换成这个小数后面的大数；
- 下一个数要满足增长的幅度尽可能小，那么小数应该是尽量靠右的数，被交换的大数应该要尽可能小，后面的数应该改为从小到大排列。
过程：
- 从后开始往前找第一个
nums[i-1] < nums[i]，nums[i, end]必然是降序; - 再从后开始往前找第一个
nums[i-1] < nums[k]，交换大数和小数； - 因为
nums[i-1] >= nums[k+1]，所以交换后的nums[i, end]还是降序，反转为升序。 - 如果本身就是降序，那么 1 的过程中找不到匹配的元素，
i = 0，同样可以使用 3 的过程反转。
Documentation
¶
Overview ¶
* @lc app=leetcode id=31 lang=golang * * [31] Next Permutation * * https://leetcode.com/problems/next-permutation/description/ * * algorithms * Medium (31.76%) * Likes: 2786 * Dislikes: 964 * Total Accepted: 324.6K * Total Submissions: 1M * Testcase Example: '[1,2,3]' * * 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 *
Source Files