卖萌的弱渣

I am stupid, I am hungry.

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1
2
3

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution

  • 第一步找出一个k，使得k之后的为递减序列。
  • 接下来，我们需要找到一个最大的下标L使得 a[k]<a[L] （就是说递减序列中最小的元素）
  • 交换a[k]和a[L]之后，对k+1之后的逆置即可（在纸上试试），这样就变成了升序。
  • eg: 1 4 3 2 k=0 L=3 swap-> 2431 逆置-> 2134
(Next-Permutation.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if len(nums) < 2:
            return
        # find the element after which the elements are descending
        k = len(nums)-2
        while k>=0:
            if nums[k] < nums[k+1]:
                break
            k -= 1

        # 5 4 3 2 1
        if k < 0:
            nums.sort()
            return

        # find the smallest nums[l] > nums[k]
        l = len(nums)-1
        while l>k:
            if nums[l] > nums[k]:
                break
            l -= 1
        nums[k],nums[l] = nums[l],nums[k]

        nums[:] = nums[:k+1] + nums[:k:-1]
(Next-Permutation.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Solution {
    public void nextPermutation(int[] nums) {
        // 找到递减序列的前一个
        if (nums.length < 2)
            return;
        int k = nums.length-2;
        while (k>=0 && nums[k] >= nums[k+1])
            k-=1;

        // 5 4 3 2 1
        if (k < 0){
            Arrays.sort(nums);
      return ;
  }
        // 找到k后面最小值
        int l = nums.length-1;
        while (l>k && nums[l]<=nums[k])
            l -=1;

        // swap a[l],a[k]
        int tmp = nums[k];
        nums[k] = nums[l];
        nums[l] = tmp;

        // reverse array after k
        reverse(nums,k+1);

    }
    public void reverse(int[] nums, int index){
        int r = nums.length-1;
        int l = index;
        while (l<r){
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
            l += 1;
            r -= 1;
        }

    }
}