1053. Previous Permutation With One Swap
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 (A swap exchanges the positions of two numbers arr[i]
and arr[j]
). If it cannot be done, then return the same array.
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.
Example 4:
Input: arr = [3,1,1,3] Output: [1,3,1,3] Explanation: Swapping 1 and 3.
Constraints:
1 <= arr.length <= 104
1 <= arr[i] <= 104
Rust Solution
struct Solution;
impl Solution {
fn prev_perm_opt1(mut a: Vec<i32>) -> Vec<i32> {
let n = a.len();
if n < 2 {
return a;
}
let mut i = n - 2;
while i > 0 && a[i] <= a[i + 1] {
i -= 1;
}
if i == 0 && a[0] <= a[1] {
return a;
}
let mut j = n - 1;
while a[j] >= a[i] || a[j] == a[j - 1] {
j -= 1;
}
a.swap(i, j);
a
}
}
#[test]
fn test() {
let a = vec![3, 2, 1];
let res = vec![3, 1, 2];
assert_eq!(Solution::prev_perm_opt1(a), res);
let a = vec![1, 1, 5];
let res = vec![1, 1, 5];
assert_eq!(Solution::prev_perm_opt1(a), res);
let a = vec![1, 9, 4, 6, 7];
let res = vec![1, 7, 4, 6, 9];
assert_eq!(Solution::prev_perm_opt1(a), res);
let a = vec![3, 1, 1, 3];
let res = vec![1, 3, 1, 3];
assert_eq!(Solution::prev_perm_opt1(a), res);
}
Having problems with this solution? Click here to submit an issue on github.