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 <algorithm>
2#include <vector>
3#include <iostream>
4
5void nextPermutation(std::vector<int>& nums) {
6 int n = nums.size(), i = n - 2;
7 while (i >= 0 && nums[i] >= nums[i + 1]) --i;
8 if (i >= 0) {
9 int j = n - 1;
10 while (nums[j] <= nums[i]) --j;
11 std::swap(nums[i], nums[j]);
12 }
13 std::reverse(nums.begin() + i + 1, nums.end());
14}
15
16int main() {
17 std::vector<int> nums = {1, 2, 3};
18 nextPermutation(nums);
19 for (int num : nums) std::cout << num << " ";
20 return 0;
21}The C++ implementation uses STL library functions for swapping and reversing parts of the array to find the next permutation. The algorithm checks for the first pattern of descent from the end of the array, swaps elements in adherence to lexicographical rules, and reverses the segment to get the minimal permutation format.