Leetcode31

题目描述

1. A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

   • For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

   The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

   • For example, the next permutation of arr = [1,2,3] is [1,3,2].
   • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
   • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

   Given an array of integers nums, find the next permutation of nums.

   The replacement must be in place and use only constant extra memory.

   Example 1:

   Input: nums = [1,2,3]
   Output: [1,3,2]
   

   Example 2:

   Input: nums = [3,2,1]
   Output: [1,2,3]
   

   Example 3:

   Input: nums = [1,1,5]
   Output: [1,5,1]
   

   Constraints:

   • 1 <= nums.length <= 100
   • 0 <= nums[i] <= 100

思路

这个问题牵涉到了线性代数 当中 对于逆序数 的 理解。具体思路在 代码当中有所体现 。

代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int size = nums.size();
        int last = nums.back();
        int tag = -1;
        for (int i= size -2 ;i >=0 ;i -- ){
            if (nums[i] < nums[i+1] ){
                tag = i;
                break ;
            }
        }
        if (tag == -1){
            sort(nums.begin(),nums.end());
            return ;//这里发现整个数组已经逆序，因此返回正序的数组即可
        }
        int second_max = -1;
        for ( int i = size-1;i >=0 ;i--){
            if (nums[i] > nums[tag]) {
                second_max = i;
                break;
            }
        }//next permutation如何获得，应当选择第一个不满足逆序的地方，倒着找到第一个比它大的数字，让它来做这一轮的老大，就可以找到下一个permutation了。想明白什么叫做老大，是很关键的。如果代码不能够理解，试图理解这一个变化。23541 的next permutation是 24135 。想想这个变化是怎么做到的，就可以解决这个问题了。
        swap (nums[tag],nums[second_max]);
        sort(nums.begin()+tag+1,nums.end());
    }
};