算法刷题笔记 Leetcode 31.下一个排列

柔情只为你懂 2024-03-24 22:56 67阅读 0赞

[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

### 下一个排列 ###

//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void nextPermutation(int[] nums) {
            //
            //① 从右向左，找到第一个"升序",改升序之后是降序的
            //② 将”升序第一个元素A“拿出来，从升序完之后的梯队里找到第一个大于A的元素
            //   替换之后 将替换A元素之后的元素 全部进行 升序排序
            int i = nums.length - 2;//?为什么-2 --- 解释 因为数组下标从0开始，我们是从倒数第2开始判断
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }
            //此时到达第一个' 升序 '的元素处
            //从后面降序处 找到比当前元素”大“的元素
            //交换元素
            if (i >= 0) {
                int j = nums.length - 1;
                while (j >= 0 && nums[j] <= nums[i]) {
                    j--;
                }
                swap(nums, i, j);
            }
            reserve(nums, i + 1);
        }
    
        static void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    
        static void reserve(int[] nums, int i) {
            int left = i, right = nums.length - 1;
            while (left < right) {
                //到这步 后面全是 ”降序“ 的数组，直接"双指针"交换位置即可
                swap(nums, left, right);
                left++;
                right--;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

这题是算法思想，主要是参考官方题解和下面这个文章[LeetCode-下一个排列\_leetcode 下一个排列\_学计算机的小花神的博客-CSDN博客][LeetCode-_leetcode _-CSDN]

### 复杂度分析 ###

**时间复杂度**：O(N)，其中 N 为给定序列的长度。我们至多只需要扫描两次序列，以及进行一次反转操作。

**空间复杂度**：O(1)，只需要常数的空间存放若干变量。

此题需要一些技巧来解题，也是[LeetCode 热题 100][LeetCode _ 100] 中的” **技巧题** “ 具体的实现思路就在代码中咯~

[LeetCode_ -]: https://leetcode.cn/problems/next-permutation/
[LeetCode-_leetcode _-CSDN]: https://blog.csdn.net/jaaccck/article/details/120238296
[LeetCode _ 100]: https://leetcode.cn/studyplan/top-100-liked/