AcWing 51. 数字排列    原题链接    中等

作者： 作者的头像   烤肠哥+order丸子 ,  2021-07-18 13:57:46 ,  所有人可见 ,  阅读 362

2


本想写个递归，但又不知道如何下手，看了@吴子涵，瞬间想到应函数做，next_permutation

class Solution {
public:
    vector<vector<int>> permutation(vector<int>& nums) {
    vector<vector<int>> res;
    res.push_back(nums);
    while(next_permutation(nums.begin(),nums.end()))
    res.push_back(nums);
    return res;
    }
};

2 评论

用户头像
666_0   6个月前         踩      回复

这里你考虑的只适合[1,2,3]情况，next_premutation函数是得到当前排列的下一种排列，就是当[1,2,3]使用这个函数时会得到[1,3,2]。但如果输入给你[3,1,2]，函数得到就是[3,2,1]，之后停止，也就是你最终得到的结果为[[3,1,2],[3,2,1]]。
在AcWing对应题目上提交你这段代码，Wrong Answer，在输入为[3,2,1]时出现了我上面说的情况，next_premutation函数找到最后一个排列终止，可以这样更改

  vector<vector<int>> res;
  sort(nums.begin(),nums.end());
        do{
              vector<int> temp(nums.begin(), nums.end());
        res.push_back(temp);
  }while(next_permutation(nums.begin(),nums.end()));
  return res;

（刚搞AcWing几天，不会评论粘代码，这是函数体）

用户头像
烤肠哥+order丸子   6个月前         踩      回复

多谢，记起来还是麻烦，感觉用递归更好