网站内页全是404,网站建设桔子科技,网站建设都是模板,深圳网站建设公司哪家比较好交换位置#xff0c;双指针#xff0c;排序。
题目 下一个排列即在组成的排列中的下一个大的数#xff0c;然后当这个排列为降序时即这个排列最大#xff0c;因为大的数在前面#xff0c;降序排列的下一个数即升序。所以#xff0c;要是想找到当前排列的下一个排列…交换位置双指针排序。
题目 下一个排列即在组成的排列中的下一个大的数然后当这个排列为降序时即这个排列最大因为大的数在前面降序排列的下一个数即升序。所以要是想找到当前排列的下一个排列肯定是先从后面开始找因为后面的数做交换才使得排列尽可能接近。可以想一下从最后一个数往回找时如果一直是升序就说明已经是最大了直到找到那个不是升序的数做交换即要操作的下一排列了交换时的数应该是扫描数组的大于目标数的最小数这样才符合原数组的下一个排列。注意从后往前找的升序即从前往后的降序找到目标数后还要处理目标数的后面序列从前往后看显然刚刚扫描的序列是降序的这样后面几个数组成的排列是最大的显然不符合下一个序列。在当前数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;}
}找准双指针扫描的范围对准目标数做操控。
