LeetCode Next Permutation

LeetCode 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,31,3,2
3,2,11,2,3
1,1,51,5,1


本题要求一个序列的下一个更大的序列,比如1,2,3 → 1,3,2,如果一个序列是最大的序列,如3,2,1,则返回其最小序列1,2,3。

算法从后往前扫描序列,如果从后往前看一直是上升的,如3,2,1,则说明这是最大的序列,直接将其逆序即可。

否则直到找到一个下降的转折点,比如4876543,找到48是下降的,这样我们就可以把4换成更大的数,但又不能太大,Next Permutation必须是紧跟在原序列后面的一个序列,所以我们从4的后面找比4大的最小的数,这里就是5。然后交换4和5,得到5876443,此时5后面仍然是有序的,而且是最大的,所以还要把5后面的序列逆序一下,得到5344678。

完整代码如下:

class Solution {
public:
	void nextPermutation(vector<int>& nums) { // 4876543
		for (int i = nums.size() - 1; i > 0; i--) {
			if (nums[i] > nums[i - 1]) { // 8 > 4
				int min_idx = i, min_val = INT_MAX;
				for (int j = nums.size() - 1; j > i; j--) {
					if (nums[j] > nums[i - 1] && nums[j] < min_val) { // 5 > 4
						min_idx = j;
						min_val = nums[j];
					}
				}
				swap(nums[i - 1], nums[min_idx]); // 5876443
				reverse(nums.begin() + i, nums.end()); // 5344678
				return;
			}
		}
		reverse(nums.begin(), nums.end());
	}
};

本代码提交AC,用时12MS。

Leave a Reply

Your email address will not be published. Required fields are marked *