LeetCode_双指针_中等_31.下一个排列

╰+攻爆jí腚メ 2023-10-06 18:06 4阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中**下一个更大的排列**。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。**必须原地修改，只允许使用额外常数空间**。

**示例 1：**  
输入：nums = \[1,2,3\]  
输出：\[1,3,2\]

**示例 2：**  
输入：nums = \[3,2,1\]  
输出：\[1,2,3\]

**示例 3：**  
输入：nums = \[1,1,5\]  
输出：\[1,5,1\]

**示例 4：**  
输入：nums = \[1\]  
输出：\[1\]

**提示：**  
1 <= nums.length <= 100[【算法】二分搜索][Link 1]  
0 <= nums\[i\] <= 100

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/next-permutation

## 2.思路 ##

（1）双指针  
思路参考该[LeetCode 用户题解][LeetCode]。

想得到当前排列在字典序中下一个更大的排列，则需要**将前面的“小数”与后面的”大数“进行交换，并且还要保证下一个数的增加幅度最小**，这样就能得到符合条件的排列。为此需要：

*  从数组后面向前找第一个升序元素对 (nums\[i\], nums\[i + 1\])，即 nums\[i\] < nums\[i + 1\]，其中从后向前找是为了**尽量在低位上交换，以保证下一个数增加的幅度最小**；
 *  在 nums\[i + 1…nums.length - 1\] 中从后向前查找第一个大于 nums\[i\] 的值 nums\[j\]，然后交换它们的值；
 *  最后将 nums\[i + 1\] ~ nums\[nums.length - 1\] 从降序变成升序即可，由于前面已经将 nums\[i\] 与 nums\[j\] (nums\[i\] < nums\[j\]) 进行了交换，即新得到的排列已经比原来的大，**但为了保证增加的幅度最小，所以需要将 nums\[i\] 后面的序列变成降序**。

> 相关知识点：  
> [【算法】二分搜索][Link 1]

## 3.代码实现（Java） ##

//思路1————双指针
    class Solution {
        
        public void nextPermutation(int[] nums) {
        
            int i = nums.length - 2;
            //从数组后面向前找第一个升序元素对(nums[i], nums[i + 1])，即 nums[i] < nums[i + 1]
            while (i >= 0 && nums[i] >= nums[i + 1]) {
        
                i--;
            }
            //若 i >= 0，则已经找到升序元素对
            if (i >= 0) {
        
                int j = binarySearch(nums, i + 1, nums.length - 1, nums[i]);
                //交换 nums[i] 和 nums[j] 的值
                swap(nums, i, j);
            }
            //将 nums[i + 1...nums.length - 1] 反转，即从降序变成升序
            reverse(nums, i + 1, nums.length - 1);
        }
        
        //在 nums[left...right](降序) 中查找大于 target 的元素的最大下标
        public int binarySearch(int[] nums, int left, int right, int target) {
        
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                if (nums[mid] > target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return right;
        }   
    
        //将 nums[i...j] 反转
        public void reverse(int[] nums, int i, int j) {
        
            while (i < j) {
        
                swap(nums, i++, j--);
            }
        }
        
        //交换 nums[i] 和 nums[j] 的值
        public void swap(int[] nums, int i, int j) {
        
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

[Link 1]: https://xgqngu.blog.csdn.net/article/details/128591151
[LeetCode]: https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/