1053. Previous Permutation With One Swap
Description
Given an array of positive integers arr
(not necessarily distinct), return the lexicographically largest permutation that is smaller than arr
, that can be made with exactly one swap. If it cannot be done, then return the same array.
Note that a swap exchanges the positions of two numbers arr[i]
and arr[j]
Example 1:
Input: arr = [3,2,1] Output: [3,1,2] Explanation: Swapping 2 and 1.
Example 2:
Input: arr = [1,1,5] Output: [1,1,5] Explanation: This is already the smallest permutation.
Example 3:
Input: arr = [1,9,4,6,7] Output: [1,7,4,6,9] Explanation: Swapping 9 and 7.
Constraints:
1 <= arr.length <= 104
1 <= arr[i] <= 104
Solutions
Solution 1: Greedy
First, we traverse the array from right to left, find the first index $i$ that satisfies $arr[i - 1] > arr[i]$, then $arr[i - 1]$ is the number we need to swap. Next, we traverse the array from right to left again, find the first index $j$ that satisfies $arr[j] < arr[i - 1]$ and $arr[j] \neq arr[j - 1]$. Now, we swap $arr[i - 1]$ and $arr[j]$ and return the array.
If we traverse the entire array and do not find an index $i$ that meets the conditions, it means the array is already the smallest permutation, so we just return the original array.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|