Permutations

我不是女神ヾ 2022-06-04 10:26 246阅读 0赞

题目

  1. Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations: 

  1. [
  2.   [1,2,3],
  3.   [1,3,2],
  4.   [2,1,3],
  5.   [2,3,1],
  6.   [3,1,2],
  7.   [3,2,1]
  8. ]
  1. Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations: 

  1. [
  2.   [1,1,2],
  3.   [1,2,1],
  4.   [2,1,1]
  5. ]

分析

1. 题目要求

题目1和题目2都是要求出给定数组的全排列，区别在于一个有重复的数字而一个没有重复的数字。

2. 求解思路

这两道题可以用相同的方法求解。

  1. 对给出的数组进行升序排序。

  2. 使用c++自带的 nexpermutation函数 依次求出下一个排列。

nexpermutation函数原型如下：

  1. #include <algorithm>
  2. bool next_permutation(iterator start, iterator end);

如果想要自己写出求解下一个排列的函数，可参照我之前写的 Next Permutation 。

3. 代码如下

  1. class Solution {
  2. public:
  3.     vector<vector<int>> permuteUnique(vector<int>& nums) {
  4.         vector<vector<int>> result;
  5.         sort(nums.begin(), nums.end());
  6.         do {
  7.             result.push_back(nums);
  8.         } while(next_permutation(nums.begin(), nums.end()));
  9.         return result;
  10.     }
  11. };

发表评论

表情：
评论列表 （有 0 条评论，246人围观）

还没有评论，来说两句吧...

相关阅读