力扣 下一个排列

交换位置，双指针，排序。

题目

下一个排列即在组成的排列中的下一个大的数，然后当这个排列为降序时即这个排列最大，因为大的数在前面，降序排列的下一个数即升序。所以，要是想找到当前排列的下一个排列，肯定是先从后面开始找，因为后面的数做交换才使得排列尽可能接近。可以想一下，从最后一个数往回找时，如果一直是升序，就说明已经是最大了，直到找到那个不是升序的数做交换，即要操作的下一排列了，交换时的数应该是扫描数组的大于目标数的最小数，这样才符合原数组的下一个排列。注意从后往前找的升序即从前往后的降序，找到目标数后，还要处理目标数的后面序列，从前往后看，显然刚刚扫描的序列是降序的，这样后面几个数组成的排列是最大的显然不符合下一个序列。在当前数do过后，后面的数应该是最小的即从前往后升序的状态。

时间复杂度： O(n)，空间复杂度： O(1)。

class Solution {public void nextPermutation(int[] nums) {int i = nums.length - 2;while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}if (i >= 0) {int j = nums.length - 1;while (j >= 0 && nums[i] >= nums[j]) {j--;}swap(nums, i, j);}reverse(nums, i + 1);}public void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public void reverse(int[] nums, int start) {int left = start, right = nums.length - 1;while (left < right) {swap(nums, left, right);left++;right--;}}
}

也可以用sort方法直接排。

class Solution {public void nextPermutation(int[] nums) {int len = nums.length;for (int i = len - 1; i >= 0; i--) {if (i == 0) {Arrays.sort(nums);return;} else {if (nums[i] > nums[i - 1]) {Arrays.sort(nums, i, len);for (int j = i; j <len; j++) {if (nums[j] > nums[i - 1]){swap(nums,j,i-1);return;}}}}}}private void swap(int[] nums, int i,int j){int tmp =nums[i];nums[i]=nums[j];nums[j]=tmp;}
}

找准双指针扫描的范围，对准目标数做操控。