YSMull
<-- algorithm



原题链接

算法介绍

算法介绍

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);
        }
    }
}