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.
1using System;
2
3class Program {
4 static void Main() {
5 int[] nums = { 1, 2, 3 };
6 NextPermutation(nums);
7 Console.WriteLine(string.Join(", ", nums));
8 }
9
10 public static void NextPermutation(int[] nums) {
11 int i = nums.Length - 2;
12 while (i >= 0 && nums[i] >= nums[i + 1]) i--;
13 if (i >= 0) {
14 int j = nums.Length - 1;
15 while (nums[j] <= nums[i]) j--;
16 Swap(nums, i, j);
17 }
18 Reverse(nums, i + 1, nums.Length - 1);
19 }
20
21 private static void Swap(int[] nums, int i, int j) {
22 int temp = nums[i];
23 nums[i] = nums[j];
24 nums[j] = temp;
25 }
26
27 private static void Reverse(int[] nums, int start, int end) {
28 while (start < end) {
29 Swap(nums, start, end);
30 start++;
31 end--;
32 }
33 }
34}This C# implementation showcases the usage of traditional array manipulation techniques. It employs a swap method for element interchange and a reverse method tailored to segmental array rearrangement.