首页 > 代码库 > Leetcode--Next Permutation

Leetcode--Next Permutation

2024-07-15 23:53:55   222人阅读

Problem Description:

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

分析：题目的意思是求字典序中的下一个排列，我们发现有以下规律：

我们知道数字的权重从个位数开始增加，我们来看下154763的154763，4和6 。 从个位开始查找，6是第一个比4大的数，且4的位数比6大，如果交换这两个数，总的值就会变大。

我们的找下一个排列的策略如下：

1.从个位开始往前查找，找到第一个逆序的值，154763中就是4。

2.再从个位开始往前查找，找到第一个比刚才逆序值大的数，这里就是6。

3.交换两个数最后会得到156743，我们发现156743并不是我们想要的数，因为156743比156347要大。

4.所以我们最后一步就是要对743进行排序，排成最小的347

5.有特殊情况，比如刚开始的数就是全逆序的，比如765431，那么下一个值是134567.

按照这一规律写出代码如下：
class Solution {
public:
    void swapp(int *a,int *b)
{
    *a^=*b;
    *b^=*a;
    *a^=*b;
}

void nextPermutation(vector<int> &num) {
        int len=num.size();
        int i,j;
        if(len==0)
            return;
        for(i=len-2;i>=0;i--)
            if(num[i]<num[i+1])
                break;

        if(i<0)
        {
            for(int s=0,p=len-1;s<p;s++,p--)
                swapp(&num[s],&num[p]);
            return;
        }
        else
        {
            for(j=len-1;j>i;j--)
                if(num[j]>num[i])
                    break;

            swapp(&num[i],&num[j]);
            for(int s=i+1,p=len-1;s<p;s++,p--)
                swapp(&num[s],&num[p]);
            return;
        }
    }
};




参考：http://www.waitingfy.com/archives/971


联系
我们