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: find out the transform pattern first. The basic idea is: scan the array from the end to the beginning to find out the first "less than" pair <num[i], num[i+1>, swap the num[i] in the pair with the the smallest element but greater than num[i] in the subarray of num[i+1, ..., n-1], where n is the size of the array num. Then, we need to reverse the subarrary num[n+1, ..., n-1]. If no such "less than" pair is found, then we can easily reverse the entire array num to get the result. [Think carefully first, and then program....]
class Solution { public: void nextPermutation(vector<int> &num) { // Note: The Solution object is instantiated only once and is reused by each test case. int n = num.size(); if(n!=0){ for(int i=n-2; i>=0; --i){ if(num[i]<num[i+1]){ int j=0, k=0; //find the smallest one but larger than num[i] in num[i+1] to num[n-1] for(j=n-1; j>i; j--) if(num[j]>num[i]){ swap(num[i], num[j]); break; } //reverse num[i+1] to num[n-1] reverse(num.begin()+i+1, num.end()); return; } } reverse(num.begin(), num.end()); } } };
No comments:
Post a Comment