LeetCode-31-Next Permutation(C语言实现)

int cmp(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}


//返回nums数组中下标l到r之间（包含l和r）比flag大的最小的数的下标
//如果没有比flag大的数则返回-1
int min(int *nums, int l, int r, int flag){
    int i, pos = -1;
    for(i = l; i <= r; ++i){
        if(nums[i] > flag){
            pos = i;
            goto step0;
        }
    }
step0:
    for(i = pos + 1; i <= r; ++i){
        if(nums[i] > flag && nums[i] < nums[pos]){
            pos = i;
        }
    }
    return pos;
}


//思路：从倒数第二位数开始依次查找该数nums[i]后面是否有大于它的数
//如果有，用min函数获得大于它的数中最小的数的下标pos，并交换nums[i]和nums[pos]
//再对第i位之后的数进行快排，即得到结果
void nextPermutation(int* nums, int numsSize) {
    bool able = false;
    int i, tmp, pos;
    for(i = numsSize - 2; i >= 0; --i){
        pos = min(nums, i + 1, numsSize - 1, nums[i]);
        if(pos != -1){
            tmp = nums[i];
            nums[i] = nums[pos];
            nums[pos] = tmp;
            qsort(&nums[i + 1], numsSize - i - 1, sizeof(int), cmp);
            able = true;
            goto step;
        }
    }
step:
    if(!able){
        for(i = 0; i < numsSize / 2; ++i){
            tmp = nums[i];
            nums[i] = nums[numsSize - 1 - i];
            nums[numsSize - 1 - i] = tmp;
        }
    }
}