31. Next Permutation

Description

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

Solutions

Solution 1: Two traversals

We first traverse the array from back to front and find the first position $i$ where $nums[i] \lt nums[i + 1]$.

Then traverse the array from back to front again and find the first position $j$ where $nums[j] \gt nums[i]$. Swap $nums[i]$ and $nums[j]$, and then reverse the elements from $nums[i + 1]$ to $nums[n - 1]$, the next permutation can be obtained.

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

The time complexity is $O(n)$ and the space complexity is $O(1)$. Where $n$ is the length of the array.

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;
        while (~i && nums[i] >= nums[i + 1]) {
            --i;
        }
        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());
    }
};

'''
>>> 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:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # next(func, -1) => default value -1
        i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
        if i != -1:
            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]
        # wrong reverse: nums[i + 1:] = nums[i + 1::-1]

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

'''
>>> 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]

func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2
	for ; i >= 0 && nums[i] >= nums[i+1]; i-- {
	}
	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]
	}
}

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

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
    const n = nums.length;
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        --i;
    }
    if (i >= 0) {
        let j = n - 1;
        while (j > i && nums[j] <= nums[i]) {
            --j;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    for (i = i + 1, j = n - 1; i < j; ++i, --j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
};

public class Solution {
    public void NextPermutation(int[] nums) {
        int n = nums.Length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        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 {

    /**
     * @param integer[] $nums
     * @return void
     */

    function nextPermutation(&$nums) {
        $n = count($nums);
        $i = $n - 2;
        while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) {
            $i--;
        }
        if ($i >= 0) {
            $j = $n - 1;
            while ($j >= $i && $nums[$j] <= $nums[$i]) {
                $j--;
            }
            $temp = $nums[$i];
            $nums[$i] = $nums[$j];
            $nums[$j] = $temp;
        }
        $this->reverse($nums, $i + 1, $n - 1);
    }

    function reverse(&$nums, $start, $end) {
        while ($start < $end) {
            $temp = $nums[$start];
            $nums[$start] = $nums[$end];
            $nums[$end] = $temp;
            $start++;
            $end--;
        }
    }
}

31 - Next Permutation

31. Next Permutation

Description

Solutions

All Problems

All Solutions

Welcome to Subscribe On Youtube

31. Next Permutation

Description

Solutions

All Problems

All Solutions