力扣31-下一个排列

链接31. 下一个排列 - 力扣LeetCode整数数组的一个排列就是将其所有成员以序列或线性顺序排列。例如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类似于计算下一个整数比如123这三位数随机排列最靠近123且比123大的整数就是132了115同理比115大的整数就是151为什么我们能脱口而出结果回溯一下我们的思考过程也许就能找到解决这题的办法以 1 2 5 4 3 为例它的下一个排列是 1 3 2 4 5首先我们为什么知道要动2因为字典序要增大2的右边有比它更大的数。其次为什么是2和3交换因为要按字典序排列3是那个比2大的数中最小的。换完之后是 1 3 5 4 2注意到5 4 2的字典序并不是最小的还要再调整为 2 4 5所以第一步我们需要做的是找到从右往左数第一个”可能增大“的数 x即 x 的右侧有比它更大的数。在刚刚的例子中x 为2显然 x 右侧的序列是单调递减的否则从右往左数第一个”可能增大“的数就必然在 x 的右侧。所以第一步相当于从右往左找 第一个 小于它右侧相邻数 的数 x第二步解决和谁交换的问题。由于下一个排列指的是按照字典序进行排列所以要交换的元素应当是 x 右侧比 x 大的数中最小的那个。由于已知 x 右侧序列是一个递减序列因此可以再次从右往左遍历找到第一个比 x 大的数 y就是要和 x 交换的数第三步交换第四步交换后y 右侧的序列必然是递减的。因为x的右边都比它自己大而y是比它大的数中最小的那个也就是说实际上y和x之间的所有数都比它俩大因此交换之后y右边唯一比它更小的只有x而在交换前右侧序列就已经递减把最小的那个换成更小的依然递减。而我们应当调整为递增才能使得字典序是变大的当中最小的那个所以把右侧序列反转即可常规情况下的四步已经考虑清楚了接下来考虑特殊情况如果当前序列已经是字典序最大的那么按照规则下一个排列就应当是字典序最小的那个怎么处理实际上如果字典序最大意味着这个序列必然单调递减而字典序最小的序列必然单调递增所以只需要将序列反转即可Javaclass Solution { public void nextPermutation(int[] nums) { int n nums.length; // 1.从右往左找第一个小于右侧相邻数的数 int i n - 2; while(i 0 nums[i] nums[i 1]) { i--; } // 如果找到了走第二步否则直接反转整个序列 if(i 0) { // 2.从右往左找第一个比 nums[i] 大的数 int j n - 1; while(nums[j] nums[i]) { j--; } // 由分析可知j 是必然可以找到的交换 int tmp nums[i]; nums[i] nums[j]; nums[j] tmp; } // 3.反转[i 1, n - 1]如果跳过了第二步此时 i 1 0, 合理 int left i 1; int right n - 1; while(left right) { int tmp nums[left]; nums[left] nums[right]; nums[right] tmp; left; right--; } } }