首页 > 其他 > 详细

Next Permutation--LeetCode

时间:2015-04-13 12:52:04      阅读:200      评论:0      收藏:0      [点我收藏+]
mplement 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

使用STL中的思路,从后往前找一对相邻的数,在一对相邻的数中第一个元素小于第二个元素,记做*i<*ii,从后往前找到第一个元素*j,是的*j>*i,然后交换*i和*j,然后交换从*II开始(包含*ii在内)到数组末尾的序列。

void Rserve(vector<int>& vec,int begin,int end)  
{  
    while(begin <= end)  
    {  
        swap(vec[begin],vec[end]);  
        begin++;  
        end--;  
    }  
}   
  
bool FindPair(vector<int>& vec,int& first,int& second)  
{  
    int last = vec.size()-1;  
    for(;last>0;last--)  
    {  
        second = last;  
        first = last-1;  
        if(vec[first] < vec[second])  
            return true;  
    }  
    return false;  
}  
  
void nextPermutation(vector<int>& vec)  
{  
    int first,second,index;  
    if(FindPair(vec,first,second))  
    {  
        index = vec.size()-1;  
        for(;index>=first;index--)  
        {  
            if(vec[index] > vec[first])  
                break;  
        }  
        swap(vec[index],vec[first]);  
        Rserve(vec,second,vec.size()-1);   
    }  
} 


Next Permutation--LeetCode

原文:http://blog.csdn.net/yusiguyuan/article/details/45023775

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!