每周一道算法题(二十五)

上周的算法题太难了，没做出来，哈哈，这周的题目难度级别是“Medium”

题目：给你一个组合，找出全排列中的下一个排列。额，这个题目需要用举例来理解。比如给你三个数字123，那么从小到大所有的组合就是123,132,213,231,312,321这六种组合，题目的意思就是，如果给你213，那么你就需要将组合变成下一个排列，即231；如果给你的组合是最后一个321，那么你就找出第一个组合123.需要注意的是不能再开辟内存空间，即不能用malloc函数。

好了，理解题意以后我们就来看看该怎么做。我的做法是从后往前找，当找到前面一个数字比后面数字小的话就把这个数字后面的数进行从小到大的排列组合(排列组合的方法用的是《每周一道算法题(十四)》 中的快排)，然后再将前面那个小数字和后面的数字的位置进行交换即可，先大概了解下思路，对比着代码来理解：

//排序
 void quickSort(int* nums,int first,int end){
    int temp,l,r;
    if(first>=end)return;
    temp=nums[first];
    l=first;r=end;
    while(l<r){
        while(l<r && nums[r]>=temp)r--;
        if(l<r)nums[l]=nums[r];
        while(l<r && nums[l]<=temp)l++;
        if(l<r)nums[r]=nums[l];
    }
    nums[l]=temp;
    quickSort(nums,first,l-1);
    quickSort(nums,l+1,end);
}

void nextPermutation(int* nums, int numsSize) {
    //如果给出的组合长度小于等于1位，直接返回
    if (numsSize <= 1) return;
    //遍历给出的组合
    for (int i = numsSize - 1; i > 0; i--) {
        //如果前面的数小于后面的数
        if (nums[i] > nums[i-1]) {
            //从前面小的那个数字(我们记为min)后面开始进行排序
            quickSort(nums,i,numsSize-1);
            //遍历排序后的数字
            for (int j = --i;j < numsSize - 1;j++) {
                //把min与后面比他大的最小数字进行交换
                if (nums[i] < nums[j+1]) {
                    int temp = nums[i];
                    nums[i] = nums[j+1];
                    nums[j+1] = temp;
                    return;
                }
            }
            return;
        }
    }
    // 如果没发现前面有比后面小的数，则将整个组合升序排列即可(即例题中的321，需要的组合是升序排列123)
    quickSort(nums,0,numsSize-1);
}

效率一般，方法有很多，有兴趣的朋友可以自己尝试。。。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!