1 题目
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
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 <= 1000 <= nums[i] <= 100
2 解答
感谢这位铁子的思路：https://www.jianshu.com/p/0fb544271bb5
说实话，这个题目没看懂....，什么下一个排列= =，我还是看了看别人的题目解释，我才知道是要干啥，还不如直接说某个整数，交换位置得到下一个接近该整数的值，当整数最大时，返回它的最小值。唉，难以费解。
那么整数的话，怎么找到它的下一个数呢？
（1）从后往前找一个 i < i+1 的
（2）没找到的话说明，数已经是最大的了，需要把这个数整体升序。 找到的话然后从右边找第一个比 i 大的（因为现在 i 到末尾的是降序的了），跟 i 进行交换 找的边界就是找到 i+1（包括自己），找到然后进行交换，肯定能找到 i+1就是一个，只是找一个更小的看有没有，交换完后，然后把 i 后的升序排列。
class Solution { public void nextPermutation(int[] nums) { // 1 当数组为空或者长度为1时，直接返回 if (nums == null || nums.length == 1) { return; } // 2 当数组长度为 2 时，直接交换 if (nums.length == 2) { swap(nums, 0, 1); return; } // 3 当数组长度大于3 // 从后往前找一个 nums[i] < nums[i+1] 的 边界点 int i = nums.length-2; while (i >= 0 && nums[i] >= nums[i+1]) { i--; } // i 大于等于0的话 说明找到了 if (i >= 0) { int j = nums.length-1; while (nums[j] <= nums[i]) { j--; } swap(nums, i, j); } // 倒序 i 后的值 // i 不存在的话就是 -1, -1+1=0,相当于升序 // i 存在的话，就是 i 后的升序排列 Arrays.sort(nums, i+1, nums.length); } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }
这个题费劲哦，不做算法的话，还真不知道找整数的下一个临界值的思路，加油。