Sponsored
Sponsored
This approach involves transforming the current permutation into its next lexicographical order. The key operations include identifying the longest non-increasing suffix and swapping elements to get a slightly larger permutation, followed by reversing the suffix to get the lowest order.
Time Complexity: O(n), where n is the number of elements in the array. This is due to the maximal traversal and operations over the array.
Space Complexity: O(1) since the operation is performed in-place with constant memory usage.
1#include <stdio.h>
2
3void swap(int *a, int *b) {
4 int temp = *a;
5 *a = *b;
6 *b = temp;
7}
8
9void reverse(int* nums, int start, int end) {
10 while (start < end) {
11 swap(&nums[start], &nums[end]);
12 start++;
13 end--;
14 }
15}
16
17void nextPermutation(int* nums, int numsSize) {
18 int i = numsSize - 2;
19 while (i >= 0 && nums[i] >= nums[i + 1]) {
20 i--;
21 }
22 if (i >= 0) {
23 int j = numsSize - 1;
24 while (nums[j] <= nums[i]) {
25 j--;
26 }
27 swap(&nums[i], &nums[j]);
28 }
29 reverse(nums, i + 1, numsSize - 1);
30 return;
31}
32
33int main() {
34 int nums[] = {1, 2, 3};
35 int numsSize = sizeof(nums) / sizeof(nums[0]);
36 nextPermutation(nums, numsSize);
37 for (int i = 0; i < numsSize; i++) {
38 printf("%d ", nums[i]);
39 }
40 return 0;
41}The provided C solution modifies the array in-place to compute the next permutation. It starts by searching for the first pair where a number is less than the immediate right neighbor, moving left from the end of the array. Upon finding this value, a subsequent search for the smallest number larger than it is performed within the right section of the array. Finally, this section is reversed to form the smallest lexicographical order possible.