Difficulty: Medium
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
language c
void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void inverse(int* array, int start, int end) { while(start < end) { swap(&array[start], &array[end]); start++; end--; } } //next_permutation函数将按字母表顺序生成给定序列的下一个较大的序列，直到整个序列为减序为止 //对序列大小的比较做出定义：两个长度相同的序列，从两者的第一个元素开始向后比较， //直到出现一个不同元素（也可能就是第它们的第一个元素），该元素较大的序列为大，反之序列为小； //若一直到最后一个元素都相同，那么两个序列相等。 //对于一个任意序列，最小的序列是增序，最大的序列为减序。 void nextPermutation(int* nums, int numsSize) { //如果只有一个元素，直接返回 if (numsSize == 1) return; int i; //从后往前找，找到第一个是非增序的元素 for(i = numsSize-1; i > 0; i--) { if(nums[i-1] < nums[i]) break; } //printf("%d\n", i); int pivot = i-1; //printf("pivot %d\n", pivot); int j; //若pivot为-1，即表示整个序列从前往后是递减的，即为最大的序列，那么下一个全排列就应该为倒过来的增序。 if(pivot == -1) { //printf("**********\n"); //i = 0; //j = numsSize - 1; inverse(nums, 0, numsSize-1); /*while(i < j) { swap(&nums[i], &nums[j]); i++; j--; }*/ } else { //printf("-------------\n"); //从后往前后遍历，找到第一个比nums[pivot]大的元素,交换他们的位置然后把pivot之后的元素倒序 j = numsSize-1; while(j > pivot ) { if (nums[j] > nums[pivot]) { //printf("%d %d\n", nums[j], nums[pivot]); swap(&nums[j], &nums[pivot]); break; //printf("%d %d\n", nums[j], nums[pivot]); } j--; } inverse(nums, pivot+1, numsSize-1); //i = pivot+1; //j = numsSize-1; /*while(i < j) { //printf("~~~~~~~~~~\n"); swap(&nums[i], &nums[j]); i++; j--; }*/ } return; }PS：这个方法是参考了另个一博主的，算是观察出来的规律。
