2021/04/02
算法介绍
rust 实现（初学）
impl Solution {
pub fn reverse(nums: &mut Vec<i32>, mut i: usize, mut j: usize) {
while i < j {
nums.swap(i, j);
i += 1;
j -= 1;
}
}
pub fn next_permutation(nums: &mut Vec<i32>) {
if nums.len() < 2 {
return;
}
let mut i = -1;
// 从右向左找第一个升序对[i,i+1]
for j in (0..=(nums.len() - 2)).rev() {
if nums[j] < nums[j + 1] {
i = j as i32;
break;
}
}
if i >= 0 {
// 从右向左找第一个比 nums[i] 大的数 nums[s]
for j in (i+1..(nums.len() as i32)).rev() {
if nums[j as usize] > nums[i as usize] {
nums.swap(i as usize, j as usize);
break;
}
}
}
Solution::reverse(nums, (i + 1) as usize, nums.len() - 1);
}
}
rust 学习迭代器之后
impl Solution {
pub fn next_permutation(nums: &mut Vec<i32>) {
// 从右向左找第一个升序对[i,i+1]
if let Some(i) = nums[..nums.len() - 1].iter().enumerate().rposition(|(pos, _)| nums[pos] < nums[pos + 1]) {
// 从右向左找第一个比 nums[i] 大的数 nums[x]
if let Some(x) = nums[(i + 1)..].iter().rposition(|item| item > &nums[i]) {
nums.swap(i, i + 1 + x);
}
&nums[i + 1..].reverse();
} else {
nums.reverse();
}
}
}
两年前写的 Java 代码
class Solution {
public static void reverse(int[] nums, int start, int end) {
int i = start;
int j = end;
while (i <= j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
i++;
j--;
}
}
public void nextPermutation(int[] nums) {
int flag = 0;
for (int i = nums.length - 1; i > 0; i--) {
if (nums[i] > nums[i - 1]) {
flag = i;
break;
}
}
if (flag == 0) { // 如果已经是逆序的了，下一个全排列是全增序的
reverse(nums, 0, nums.length - 1);
} else {
for (int i = nums.length - 1; i >= flag; i--) {
if (nums[i] > nums[flag-1]) {
int tmp = nums[i];
nums[i] = nums[flag-1];
nums[flag-1] = tmp;
break;
}
}
reverse(nums, flag, nums.length - 1);
}
}
}