Next Permutation

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

题目简要：题目涉及到的是全排列问题，全排列的方法有很多，每种全排列的方法得到的排列顺序不同，但是对于一种全排列顺序而言，下一个排列指的是我们所用的排列方法得到一个排列顺序，指定一个排列，它在得到的排列顺序中的下一个排列是什么？本题目是按字典法进行的。

如1,2,3进行全排列为：

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

这样我们指定一个排列为1,2,3，那么它的下一个排列就是1,3,2.

具体做法：以5,4,7,5,3,2为例，

　　5,4,7,5,3,2是一个排列，并且我们知道一个排列是有规律的，一个排列是有规律的，一个排列可以分为两个部分（其中一个部分可以为空），其中部分一定是递减顺序的，而另一个也是递减顺序的。5，4是递减的，7,5,4,3是递增的。

　　要想得到下一个排列，首先我们必须知道将要变动的值是那个。全排的最后一个序列一定是递减顺序的，所以排列两部分中递减顺序的哪部分一定不需要改变，所以我们首先要找到id一个非递减顺序的值，也就是4位置为1，然后找到要和4交换的值，这个值是要在4之后的那个值中查找，要求是大于4的最小的那个，又因为我们是从右向做的查找，所以第一个大于4的即可。交换位置后，对位置1后面的序列进行排序。排序的原因是由字典排序的特性，如1,2,3时，当第一值变为2的时候为2,1,3, 2 后面的序列一定是从小到大的排序的，所以当我们交换两个值后要进行排序。又因为这个算法不看排序方法的时候时间复杂度为O(n),所以这个算法的时间复杂度取决于你的排序算法的时间复杂度。

void Sort(int* arr,int low ,int high)

{

    if(low>=high)return ;

    int val=arr[low];

    int i=low;

    int  j=high;

    while(i<j){

        while(i<j&&arr[j]>val)j--;

        arr[i]=arr[j];

        while(i<j&&arr[i]<=val)i++;

        arr[j]=arr[i];

    }

    arr[i]=val;

    Sort(arr,low,i-);

    Sort(arr,i+,high);

}

void nextPermutation(int* nums, int numsSize) {

    if(numsSize<=)return ;

    int i=numsSize-;

    while(i>)

    {

        if(nums[i]>nums[i-])break;

        i--;

    }

    printf("%d\n",nums[i-]);

    if(i<=)Sort(nums,,numsSize-);

    else{

        for(int j=numsSize-;j>=i;j--)

            if(nums[i-]<nums[j]){

                nums[i-]+=nums[j];

                nums[j]=nums[i-]-nums[j];

                nums[i-]-=nums[j];

                Sort(nums,i,numsSize-);

                break ;

            }

    }

}

巴特西

Next Permutation

最新文章

热门文章