题目概览整数数组的一个排列就是将其所有成员以序列或线性顺序排列。例如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来源31. 下一个排列 - 力扣LeetCode解题分析方法两次遍历以 [ 1,2,3,6,5,4 ] 为例他的下一个排列是 [ 1,2,4,3,5,6 ]可以看出一个排列中至少存在一个升序排列一个降序排列我们把共同的元素算给降序排列那么下一个排列就是将 最右侧升序排列中的最大值令此时索引为 i与 最右侧的降序排列中的较小值令此时索引为 jnums[ j ] 一定要大于 nums[ i ] 且 nums [ j ] 最小进行交换 然后将 i 后面的排列调整为升序原本已经为降序反转即可。具体实现从右侧开始遍历找到第一个相邻且满足 nums[ i ] nums[ j ] 的位置此时 [ i, j ] 就为右侧第一个升序排列[ j, n-1 ] 就为右侧第一个降序排列i 就是升序排列中的最大值。从右侧开测遍历找到第一个满足 num[ i ] nums[ k ] 的位置k 就是降序排列中较小值。交换 i 和 k反转 [ i 1, n-1 ]。时间复杂度O(n)空间复杂度O(1)class Solution { public void nextPermutation(int[] nums) { int n nums.length; if (n 1) { return; } int i n - 2, j n - 1; while(i 0 nums[i] nums[j]) { i--; j--; } if (i 0) { for (int z 0; z n / 2; z) { swap(nums, z, n - 1 - z); } return; } int k n - 1; while(nums[i] nums[k]) { k--; } swap(nums, i, k); int l n - 1; for (int z i 1; z (n i) / 2; z) { swap(nums, z, l--); } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } } 新乡本地动态 ← 返回资讯列表
