[LeetCode] 31. Next Permutation

轉自LeetCode

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,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

<Solution>

這題看到 lexicographical order，然後要求下一個排列是什麼，並且要 in-place

直覺就是用 next_permutation

code 如下

	class Solution {
	public:
	void nextPermutation(vector<int>& nums) {
	if(nums.empty()) {
	return;
	}
	next_permutation(nums.begin(), nums.end());
	}
	};

view raw nextPermutation_1.cpp hosted with ❤ by GitHub

那如果不用 next_permutation呢？

就要用個演算法來檢查 (參考資料1，參考資料2)

因為是要求 lexicographical 的下一個排序，所以在字典順序上的改變愈少愈好

用例子說明

0  1  2  5  3  3  0 的下一個排序是 0  1  3  0  2  3  5

以下是分析

• 從後往前找到第一個不是升冪到數字 pivot_1

     0  1  2  5  3  3  0

• 再從後往前找到第一個大於 pivot_1 的數字 pivot_2

     0  1  2  5  3  3  0

• swap pivot_1 和 pivot_2

     0  1  3  5  3  2  0

• 然後將 pivot_1 之後的數字做 reverse，把它變成 increasing order。因為 increasing order 在 lexicographical order 來說是小於 decreasing order 的

    0  1  3  0  2  3  5

這樣就找到 next permutation 了

code 如下

c++

	class Solution {
	public:
	void nextPermutation(vector<int>& nums) {
	if(nums.empty() || nums.size() == 1) {
	return;
	}
	//> find index of first number which breaks the increasing order
	//> start from the tail
	int pivot_1 = nums.size() - 2;
	while(pivot_1 >= 0 && nums[pivot_1] >= nums[pivot_1 + 1]) {
	--pivot_1;
	}
	//> the input is already in decreasing order, just swap all the nums
	if(pivot_1 < 0) {
	int left = 0, right = nums.size() - 1;
	while(left < right) {
	swap(nums[left], nums[right]);
	++left;
	--right;
	}
	return;
	}
	//> find index of first number which is greater than pivot_1
	//> start from the tail
	int pivot_2 = nums.size() - 1;
	while(nums[pivot_1] >= nums[pivot_2]) {
	--pivot_2;
	}
	//> swap pivot_1 and pivot_2
	swap(nums[pivot_1], nums[pivot_2]);
	//> reverse nums after position of pivot_1
	int left = pivot_1 + 1;
	int right = nums.size() - 1;
	while(left < right) {
	swap(nums[left], nums[right]);
	++left;
	--right;
	}
	}
	};

view raw nextPermutation_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun nextPermutation(nums: IntArray): Unit {
	var anchor1 = nums.lastIndex - 1
	while(anchor1 >= 0 && nums[anchor1] >= nums[anchor1+1]) {
	--anchor1
	}
	if(anchor1 < 0) {
	nums.sort()
	return
	}
	var anchor2 = nums.lastIndex
	while(nums[anchor1] >= nums[anchor2]) {
	--anchor2
	}
	nums[anchor1] = nums[anchor2].also { nums[anchor2] = nums[anchor1] }
	++anchor1
	anchor2 = nums.lastIndex
	while(anchor1 < anchor2) {
	nums[anchor1] = nums[anchor2].also { nums[anchor2] = nums[anchor1] }
	++anchor1
	--anchor2
	}
	}
	}

view raw next_permutation.kt hosted with ❤ by GitHub