leetcode31：下一个排列

题目链接

leetcode

题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如：arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，[1,2,3] 的下一个排列是 [1,3,2] 。
• [2,3,1] 的下一个排列是 [3,1,2] 。
• [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

已知：一个整数数组 nums ，找出 nums 的下一个排列。
要求：必须原地修改，只允许使用额外常数空间。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printArray(const vector<int>& nums) {
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
}

/*
    找规律

    从后往前寻找第一个出现降序的位置，
    这个位置的前一个位置与与后边某个大于它的数字交换，
    再把该位置之后调整为升序。

    时间复杂度：O(n)
        查找递减点，O(n)
        查找大于递减点的最小值，O(n)
        翻转，O(n)
    空间复杂度：O(1)
        使用了常数级别的额外空间。
*/
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 1;
        // 从后向前查找第一个降序的位置（下降点）
        while (i > 0 && nums[i - 1] >= nums[i]) i --;

        if (i <= 0) {
            reverse(nums.begin(), nums.end());
        } else {
            int j = i;
            // 若找到第一个数，则从后向前查找第一个大于它的数（交换点）
            while (j < n && nums[j] > nums[i - 1]) j ++;
            swap(nums[i - 1], nums[j - 1]);
            reverse(nums.begin() + i, nums.end());
        }
    }
};

/*
    思路同上

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution_1 {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.size() < 2) return;

        // 从后向前查找第一个降序的位置（下降点）
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i --;
        }

        if (i >= 0) {
            // 若找到第一个数，则从后向前查找第一个大于它的数（交换点）
            int j = nums.size() - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j --;
            }
            swap(nums[i], nums[j]);
        } 
        // 反转 i 之后的部分
        reverse(nums.begin() + i + 1, nums.end());
    }
};


int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,2,3},
        {3,2,1},
        {1,1,5}
    };

    for (int i = 0; i < nums_cases.size(); i ++) {
        vector<int> nums = nums_cases[i];
        cout << "Input: ";
        printArray(nums);
        solution.nextPermutation(nums);
        cout << "Output: ";
        printArray(nums);
    }
    
    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   从后向前查找第一个升序对：
       从数组的末尾开始向前查找，找到第一个满足 nums[i] < nums[i+1] 的位置 i。
       如果找不到这样的位置，说明数组已经是降序排列，直接反转整个数组即可。
   从后向前查找第一个大于 nums[i] 的元素并交换：
       如果找到了升序对，从数组的末尾开始向前查找，找到第一个满足 nums[j] > nums[i] 的位置 j。
       交换 nums[i] 和 nums[j]。
   反转 i 之后的部分：
       将 i 之后的部分反转，使其变为最小的升序排列。

   时间复杂度：O(n)
       第一步和第二步的时间复杂度为 O(n)，其中 n 是数组的长度。
       第三步的时间复杂度为 O(n)。
       总时间复杂度为 O(n)。
   空间复杂度：O(1)
       使用了常数级别的额外空间，空间复杂度为 O(1)。
*/
// nextPermutation 生成下一个排列
func nextPermutation(nums []int) {
	n := len(nums)
	if n <= 1 {
		return
	}

	// 第一步：从后向前查找第一个升序对
	i := n - 2
	for i >= 0 && nums[i] >= nums[i+1] {
		i --
	}

	// 第二步：如果找到了升序对，从后向前查找第一个大于 nums[i] 的元素并交换
	if i >= 0 {
		j := n - 1
		for nums[j] <= nums[i] {
			j--
		}
		nums[i], nums[j] = nums[j], nums[i]
	}

	// 第三步：反转 i 之后的部分
	reverse(nums, i + 1, n - 1)
}

// reverse 反转数组的指定部分
func reverse(nums []int, start, end int) {
	for start < end {
		nums[start], nums[end] = nums[end], nums[start]
		start ++
		end --
	}
}

func main() {
	// 测试用例
	testCases := []struct {
		nums    []int
		expected []int
	}{
		{
			nums:    []int{1, 2, 3},
			expected: []int{1, 3, 2},
		},
		{
			nums:    []int{3, 2, 1},
			expected: []int{1, 2, 3},
		},
		{
			nums:    []int{1, 1, 5},
			expected: []int{1, 5, 1},
		},
	}

	for i, tc := range testCases {
		nextPermutation(tc.nums)
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)

		if fmt.Sprint(tc.nums) == fmt.Sprint(tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, tc.nums)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, tc.nums, tc.expected)
		}
	}
}