lintcode 15 全排列

class Solution {
public:
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int>> permute(vector<int> &nums) {
        // write your code here
        vector<vector<int>> res;
        if(nums.size() < 2)
        {
            res.push_back(nums);
            return res;
        }
        help(res,0,nums.size(),nums);
        return res;
    }
    
    void help(vector<vector<int>>& res,int begin,int end,vector<int> &nums)//得到从begin开始的全排列
    {
        if(begin == end){                      //基本情况  
            res.push_back(nums);             
        }else{
            for(int i = begin;i < end;i++){//遍历整个数组
                swap(nums[begin],nums[i]);//把被遍历的数放在首位
                help(res,begin+1,end,nums);//求首位之后的所有排列情况
                swap(nums[begin],nums[i]);//恢复原始数组
            }
        }
    }
    void swap(int& a,int& b){
        int temp = a;
        a = b;
        b = temp;
    }
};

递归算法思路:对数据[1,2,3],需要一次遍历;每次遍历,确定首位,[1,...];[2,...];[3,...]然后通过递归得到后面的所有排列情况,对于数组中有重复元素的情况,我们只要保证,重复元素只能有一次作为子问题的开头元素,这样我们就可以避免重复计算。

非递归算法思路:https://www.cnblogs.com/answeryi/archive/2011/10/12/2209058.html
字典排序 注意 逆序的步骤不要错过

class Solution {
public:
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    vector<vector<int>> permute(vector<int> &nums) {
        // write your code here
        vector<vector<int>> res;
        if(nums.size() < 2){
            res.push_back(nums);
            return res;
        }
        sort(nums.begin(),nums.end());
        int point = -1;
        res.push_back(nums);
        while((point = findpoint(nums)) != -1){
            int next = findnext(nums,point);
            swap(nums[point-1],nums[next]);
            diandao(nums,point);
            res.push_back(nums);
        }
        return res;
    }
    int findpoint(vector<int> &nums){
        int len =  nums.size();
        for(int i = len-1;i >0;i--){
            if(nums[i] > nums[i-1])
                return i;
        }
        return -1;
    }
    int findnext(vector<int> &nums,int point){
        int len  = nums.size();
        int i  = 0;
        for(i = point; i < len;i++){
            if(nums[point-1] > nums[i]){
                return i-1;
            }
        }
        return i-1;
    }
    void  diandao(vector<int> &nums,int point){
        int j = nums.size()-1;
        int i = point;
        while(i < j){
            swap(nums[i],nums[j]);
            i++;
            j--;
        }
    }
    void swap(int& a,int& b){
        int temp;
        temp = a;
        a = b;
        b = temp;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1)这本书为什么值得看: Python语言描述,如果学的Python用这本书学数据结构更合适 2016年出版,内容...
    孙怀阔阅读 12,627评论 0 15
  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 6,004评论 0 13
  • 任之行于英彬日精进分享 显现-练习——使用 我行,一切行,我行任之行 选好人,做对事 懂人事 体验价值从满足身...
    于英彬阅读 224评论 0 0
  • 人性看的太透,反而不知道怎么讲,也不是好事。 要我觉得,看透一点多就好。不太多,也不太少。而且这种看透的沼泽,也不...
    叶脊阅读 129评论 0 0
  • 每天提升能量并更加的连接:1.持续读每天的功课,活在功课或富足录音里;2.冥想;3.每天分享奇迹;4.活在当下,接...
    海波完美旅程阅读 216评论 0 1