47. Permutations II

发表于 | 分类于

每日一题 2019 - 03 - 29

题目：

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

1
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解答：

这个题让我们对给定的序列进行全排列，不过这个序列里可能会有重复的元素，所以解题思路有两种：

  • 思路一：
    • 在往 ans 中已经进行push_back时候 find 一下 ans 中是否已经有当前的 temp 待存序列
  • 思路二：
    • 在每次进行permute时候，从全排列起始的位置到当前待排位置的前一位进行查重，如果有重复的就证明存在重复序列，就不能进行排列

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 思路一 代码
class Solution {
public:
    void test_permute(vector<int>&nums, vector<vector<int>>& ans, int begin, int end){
        if(begin == end){//完成一次完整的排列，就把此时的nums压入到ans中
            if(ans.end() == find(ans.begin(),ans.end(),nums))
                ans.push_back(nums);
            return;
        }else{
            for(int i = begin; i <= end; i++){
                swap(nums[begin],nums[i]);
                test_permute(nums,ans,begin+1,end);
                swap(nums[begin],nums[i]);
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        int len = nums.size()-1;
        test_permute(nums, ans, 0, len);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 思路二 代码
class Solution {
public:
    bool check(vector<int> &num, int start, int end, int target) {
        for(int i = start; i <=end; ++i) {
            if (num[i] == num[target])
                return false;
        }
        return true;
    }
    void test_permute(vector<int>&nums, vector<vector<int>>& ans, int begin, int end){
        if(begin == end){//完成一次完整的排列，就把此时的nums压入到ans中
            ans.push_back(nums);
            return;
        }else{
            for(int i = begin; i <= end ; i++){
                if(check(nums,begin,i-1,i)){
                    swap(nums[begin],nums[i]);
                    test_permute(nums,ans,begin+1,end);
                    swap(nums[begin],nums[i]);
                }
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        int len = nums.size()-1;
        test_permute(nums, ans, 0, len);
        return ans;
    }
};
0%
undefined