leetcode 31. Next Permutation

Bertha 。 2022-06-09 09:40 145阅读 0赞

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.  
1,2,3 → 1,3,2  
3,2,1 → 1,2,3  
1,1,5 → 1,5,1

题意就是寻找全排列的下一个元素序列。

这道题我是网上参考的答案做得，不太理解，还需要想一想。

代码如下：

public class Solution 
    {           
        public void nextPermutation(int[] nums)
        {
            if(nums==null || nums.length<=1)
                return ;
            int i=nums.length-2;
            //从后向前遍历，找到第一个不是递增的点的位置，记为p，这里是>=是考虑到重复的数据
            while(i>=0 && nums[i] >= nums[i+1])
                i--;
    
            if(i>=0)
            {
                //从p向后找，找到第一个比p对应的数小的位置，目的是找到在比p大的数中最小的数
                int j=i+1;
                while(j<nums.length && nums[j]>nums[i])
                    j++;
                // 位置j就是比p小的数，j-1就是我们要找的在比p大的数中最小的数
                j=j-1;
                int tmp=nums[j];
                nums[j]=nums[i];
                nums[i]=tmp;
    
                //把p之后的数字做逆序处理，这样就可以得到目标值
                reverse(nums, i+1);
            }else
                reverse(nums,0);
        }
    
    
    
        //逆序处理
        public void reverse(int[] nums, int beg)
        {
            int i=beg,j=nums.length-1;
            while(i < j)
            {
                int tmp=nums[j];
                nums[j]=nums[i];
                nums[i]=tmp;
                i++;
                j--;
            }
    
        }
    }

下面是C++的做法，不太懂为什么这么做，我也是参考网上的一个做法，

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        void nextPermutation(vector<int>& nums) 
        {
            if (nums.size() <= 1)
                return;
    
            int i = nums.size() - 2;
            while (i >= 0 && nums[i] >= nums[i + 1])
                i--;
            if (i >= 0)
            {
                int j = i + 1;
                while (j < nums.size() && nums[j]>nums[i])
                    j++;
                j = j - 1;
                swap(nums, i, j);
                reverse(nums, i+1);
            }
            else
                reverse(nums, 0);
        }
    
        void reverse(vector<int>& nums, int beg)
        {
            int i = beg, j = nums.size() - 1;
            while (i < j)
            {
                swap(nums, i, j);
                i++;
                j--;
            }
        }
    
        void swap(vector<int>& nums, int i, int j)
        {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    };