Question

Formatted question description: https://leetcode.ca/all/31.html

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

Algorithm

This question lets us find the next sort order. As can be seen from the example given in the question, if the given array is in descending order, it means that it is the last case of the full order, and the next order is the initial case. You can see The previous blog Permutations. Look at the following example again, there is an array as follows

1　　2　　7　　4　　3　　1

The next arrangement is:

1　　3　　1　　2　　4　　7

So how did we get it? By observing the original array, we can find that if we look forward from the end, the number gradually increases, and then decreases at 2, and then we look for the first number greater than 2 from the back, which is 3, then we exchange 2 and 3, and then transpose all the numbers after 3 at this time, the steps are as follows:

1　　2　　7　　4　　3　　1

1　　2　　7　　4　　3　　1  <= find 2, since 2<7

1　　3　　7　　4　　2　　1  <= find 3 >2 from right, swap 2,3

1　　3　　1　　2　　4　　7  <= reverse 7,4,2,1 to 1,2,4,7

Code

import java.util.Arrays;

public class Next_Permutation {

    // time: O(N^2)
    // space: O(1)
    public class Solution {

        public void nextPermutation(int[] nums) {

            if (nums == null || nums.length == 0) {
                return;
            }

            // 总体目标是，高位的小数字，换低位的大数字，才能得到next
            for (int i = nums.length - 2; i >= 0; --i) { // 3, 4, 5, 2, 1 // 注意. i < Len - 1. 也就是停在倒数第二个
                if (nums[i] < nums[i + 1]) { // 第一个波峰波谷 => 4
                    for (int j = nums.length - 1; j > i; --j) {
                        if (nums[j] > nums[i]) {
                            // 找到第一个比nums-i大的数 => 5
                            swap(nums, i, j); // 3,5,4,2,1

                            // reverse 因为剩下部分肯定是从大到小
                            // 找到第一个比nums-i大的数的一步，相当于是排序，找insert position
                            reverse(nums, i + 1, nums.length - 1); // [4,2,1] reverse to [1,2,4] => 3, 5, 1, 2, 4
                            return;
                        }
                    }

                }
            }

            reverse(nums, 0, nums.length - 1); // for没有return，就整个翻转
        }

        private void swap(int[] nums, int i, int j) {

            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;

        }

        private void reverse(int[] nums, int i, int j) {

            while (i < j) {

                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;

                i++;
                j--;
            }
        }
    }
}

############

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        for (; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
        }
        if (i >= 0) {
            for (int j = n - 1; j > i; --j) {
                if (nums[j] > nums[i]) {
                    swap(nums, i, j);
                    break;
                }
            }
        }

        for (int j = i + 1, k = n - 1; j < k; ++j, --k) {
            swap(nums, j, k);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[j];
        nums[j] = nums[i];
        nums[i] = t;
    }
}

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i = n - 2;
        for (; ~i; --i) if (nums[i] < nums[i + 1]) break;
        if (~i) {
            for (int j = n - 1; j > i; --j) {
                if (nums[j] > nums[i]) {
                    swap(nums[i], nums[j]);
                    break;
                }
            }
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

'''
>>> a=[1,2,3]
>>> reversed(a)
<list_reverseiterator object at 0x108458be0>
>>> list(reversed(a))
[3, 2, 1]

# but, use reversed(a) to directly assign values is ok
>>> b=[4,5,6,7,8]
>>> b[:3] = reversed(a)
>>> b
[3, 2, 1, 7, 8]
'''
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        if not nums:
            return
        
        # 总体目标是，高位的小数字，换低位的大数字，才能得到next
        for i in range(len(nums)-2, -1, -1):  # 3, 4, 5, 2, 1
            if nums[i] < nums[i+1]:  # 第一个波峰波谷 => 4
                j = next(j for j in range(len(nums)-1, i, -1) if nums[j] > nums[i])  # 找到第一个比nums-i大的数 => 5
                nums[i], nums[j] = nums[j], nums[i]  # 3,5,4,2,1

                # reverse 因为剩下部分肯定是从大到小
                # 找到第一个比nums-i大的数的一步，相当于是排序，找insert position
                nums[i+1:] = reversed(nums[i+1:])  # [4,2,1] reverse to [1,2,4] => 3, 5, 1, 2, 4
                return
        
        nums.reverse()  # for没有return，就整个翻转

###########


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        to_left = [i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]]

        if not to_left:
            nums = nums[::-1]
            return

        i = max(to_left)
        if i >= 0:
            to_right = [ j for j in range(n - 1, i, -1) if nums[j] > nums[i] ]
            j = to_right[0]
            nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = nums[i + 1::-1]

'''
>>> i = 3
>>> ~i
-4
>>> bool(~i)
True
#######################

>>> j = -1
>>> ~j
0
>>> bool(~j)
False
#######################

>>> a = (i for i in range (10, -1, -1) if i < 6)
>>> a
<generator object <genexpr> at 0x10a17eeb0>
>>> next(a)
5
>>>
>>>
>>> b = (i for i in range (10, -1, -1) if i < 0)
>>> next(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> next(b, -1)
-1
>>>
'''
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
        if ~i:
            j = next((j for j in range(n - 1, i, -1) if nums[j] > nums[i]))
            nums[i], nums[j] = nums[j], nums[i]
        nums[i + 1:] = nums[i + 1::-1]


############


class Solution(object):
  def nextPermutation(self, nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    if nums is None or len(nums) <= 1:
      return

    pos = None
    p = len(nums) - 2
    # find the first number that is not in correct order
    while p >= 0:
      if nums[p + 1] > nums[p]:
        pos = p
        break
      p -= 1

    if pos is None:
      self.reverse(nums, 0, len(nums) - 1)
      return

    # find the min value in the rest of the array
    minPos, minV = pos + 1, nums[pos + 1]
    for i in range(pos + 1, len(nums)):
      if nums[i] <= minV and nums[i] > nums[pos]:
        minV = nums[i]
        minPos = i
    # swap the two above number and reverse the array from `pos`
    nums[pos], nums[minPos] = nums[minPos], nums[pos]
    self.reverse(nums, pos + 1, len(nums) - 1)

  def reverse(self, nums, start, end):
    while start < end:
      nums[start], nums[end] = nums[end], nums[start]
      start += 1
      end -= 1

func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2
	for ; i >= 0; i-- {
		if nums[i] < nums[i+1] {
			break
		}
	}
	if i >= 0 {
		for j := n - 1; j > i; j-- {
			if nums[j] > nums[i] {
				nums[i], nums[j] = nums[j], nums[i]
				break
			}
		}
	}
	for j, k := i+1, n-1; j < k; j, k = j+1, k-1 {
		nums[j], nums[k] = nums[k], nums[j]
	}
}

public class Solution {
    public void NextPermutation(int[] nums) {
        var index1 = -1;
        var index2 = 0;
        for (var i = 1; i < nums.Length; ++i)
        {
            if (nums[i - 1] < nums[i])
            {
                index1 = i - 1;
                index2 = i;
            }
            else if (index1 >= 0 && nums[index1] < nums[i])
            {
                index2 = i;
            }
        }

        if (index1 >= 0)
        {
            var temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
        System.Array.Sort(nums, index1 + 1, nums.Length - index1 - 1);
    }
}

function nextPermutation(nums: number[]): void {
    const n = nums.length;
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        --i;
    }
    if (i >= 0) {
        for (let j = n - 1; j > i; --j) {
            if (nums[j] > nums[i]) {
                [nums[i], nums[j]] = [nums[j], nums[i]];
                break;
            }
        }
    }
    for (let j = n - 1; j > i; --j, ++i) {
        [nums[i + 1], nums[j]] = [nums[j], nums[i + 1]];
    }
}

31 - Next Permutation

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions