Lintcode: next permutation

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Have you met this question in a real interview? 

Yes

Example

For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Note

The list may contains duplicate integers.

Tags Expand 

LintCode Copyright Permutation

Reference:
http://blog.csdn.net/m6830098/article/details/17291259
http://algorithm.yuanbin.me/zh-cn/exhaustive_search/next_permutation.html

Pure mathematical problem, key is to understand Lexicographical algorithm
Time: O(n) + O(n) + O(n) = O(n)
Space: O(1)

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 42 43 44

class Solution { public: /** * @param nums: An array of integers * @return: An array of integers that's next permuation */ vector<int> nextPermutation(vector<int> &nums) { // write your code here int left; if(nums.size()<2) return nums; for(int i = nums.size() - 2; i >= 0; i--){ if(nums[i] < nums[i + 1]) { left = i; break; } if(i == 0){ reverse(nums, 0, nums.size() - 1); return nums; } } int right = 0; for(int i = nums.size() - 1; i > left; i--){ if(nums[i] > nums[left]) { right = i; break; } } swap(nums, left, right); reverse(nums, left + 1, nums.size() - 1); return nums; } private: void swap(vector<int>& nums, int left, int right){ if(left == right) return; int temp = nums[left]; nums[left] = nums[right]; nums[right]= temp; } void reverse(vector<int>& nums, int start, int end){ for(int i = start, j = end; i < j; i++, j--){ swap(nums, i, j); } } };

Lintcode second:
O(n)

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 42

class Solution { public: /** * @param nums: An array of integers * @return: An array of integers that's next permuation */ vector<int> nextPermutation(vector<int> &nums) { // write your code here //find the first nums[k] < nums[k + 1] //int k = nums.size() - 1; //if cannot find , k = -1 if(nums.size() <= 1) return nums; int k = nums.size() - 2; for(; k >= 0; k--){ if(nums[k] < nums[k + 1]) break; } //find nums[l] from right to left that is larger than k, int j = nums.size() - 1; for(; k > -1 && j > k; j--){ if(nums[j] > nums[k]) { swap(nums, k, j); break; } } //reorder from k + 1 to nums.end reorder(k + 1, nums); return nums; } void swap(vector<int> &nums, int k, int j){ int temp = nums[k]; nums[k] = nums[j]; nums[j] = temp; } void reorder(int start, vector<int> &nums){ int end = nums.size() - 1; while(start < end){ swap(nums, start, end); start++; end--; } } };

全排列
http://blog.csdn.net/m6830098/article/details/17320819