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.
1import java.util.Arrays;
2
3public class NextPermutation {
4 public void nextPermutation(int[] nums) {
5 int i = nums.length - 2;
6 while (i >= 0 && nums[i] >= nums[i + 1]) i--;
7 if (i >= 0) {
8 int j = nums.length - 1;
9 while (nums[j] <= nums[i]) j--;
10 swap(nums, i, j);
11 }
12 reverse(nums, i + 1);
13 }
14
15 private void reverse(int[] nums, int start) {
16 int end = nums.length - 1;
17 while (start < end) {
18 swap(nums, start, end);
19 start++;
20 end--;
21 }
22 }
23
24 private void swap(int[] nums, int i, int j) {
25 int temp = nums[i];
26 nums[i] = nums[j];
27 nums[j] = temp;
28 }
29
30 public static void main(String[] args) {
31 int[] nums = {1, 2, 3};
32 new NextPermutation().nextPermutation(nums);
33 System.out.println(Arrays.toString(nums));
34 }
35}This Java solution finds the next permutation by iterating through the array from right to left, pinpointing the first decrease. The detected element is swapped with an element on the right that is just larger, and the trailing segment is reversed.