# Next-Permutation

Oct 10, 2017

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

1,2,5,4,3 -> 1,3,2,4,5 1,3,2,5,4 -> 1,3,4,2,5

• 我们从后向前找一个最长升序序列nums[i:]
• 如果i=0，按照题目要求，我们就应该给出一个最小的组合，就直接对nums进行排序即可。
• 如果i!=0，那么我们从后向前找第一个比nums[i-1]大的数字nums[k]，而且我们肯定能找出。交换nums[i-1]nums[k],然后再对nums[i:]进行一个排序即可。
void nextPermutation(vector<int>& nums) {
for(int i = nums.size() - 1;i > 0;i--){
if (nums[i-1] < nums[i]){
int key = nums[i -1];
int j;
for(j = i;j < nums.size() && nums[j] > key;j++)
/*do nothing*/;
cout << nums[j-1] <<" " << nums[i-1];
swap(nums[j-1],nums[i-1]);
sort(nums.begin() + i,nums.end());
return ;
}
}
sort(nums.begin(),nums.end());
}


void nextPermutation(vector<int>& nums) {
int i,j = -1;
for(i = nums.size() - 1;i > 0 && nums[i-1]>= nums[i] ;i--)
/*do nothing*/;

int first = i,last = nums.size()-1;

while(first <= last) {
if (i > 0 && nums[last] > nums[i-1]) {
swap(nums[i-1],nums[last]);
break;
} else if (i > 0 && nums[first+1] <= nums[i-1] ) {
swap(nums[i-1],nums[first]);
break;
}
swap(nums[first++],nums[last--]);
}
while(first < last)
swap(nums[first++],nums[last--]);
return ;
}


void nextPermutation(vector<int>& nums) {
if (nums.size() < 2) return ;
int i,j = -1;
for(i = nums.size() - 1;i > 0 && nums[i-1]>= nums[i] ;i--)
/*do nothing*/;

int first = i,last = nums.size()-1;
while(first < last)
swap(nums[first++],nums[last--]);
//cout << i << endl;
if (i > 0) {
auto beg = nums.begin() + i;
auto it = lower_bound(beg,nums.end(),nums[i-1]);
//cout << *it << endl;
while (*it == nums[i-1])
it++;
//cout << *it << nums[i-1] << endl;
swap(*it,nums[i-1]);
}
return ;
}


LeetCodeLeetCode

Search for a Range

Search-in-Rotated-Sorted-Array