欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

46、47-Permutations

程序员文章站 2022-07-12 12:34:41
...

难度:medium

题目描述

46-Permutations I:

46、47-Permutations

47-Permutations II:

46、47-Permutations

算法分析

46:
直接使用函数next_permutation(_vector.begin(), _vector.end())
47:
在46题的基础上,使用二层循环,对得到的全排列两两进行比较,删除重复的排列

代码实现

46:

//  use function next_permutation
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.begin()+nums.size());
        do {
            result.push_back(nums);
        } while (next_permutation(nums.begin(), nums.begin() + nums.size()));
        return result;
    }
};

47:

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.begin()+nums.size());
        do {
            result.push_back(nums);
        } while (next_permutation(nums.begin(), nums.begin() + nums.size()));
        int n = result.size();
        for (int i = 0; i < result.size(); ++i) {
            for (int j = i + 1; j < result.size(); ++j) {
                if (isSame(result[i], result[j]))
                    result.erase(result.begin() + j);
            }
        }
        return result;
    }
    bool isSame(vector<int> a, vector<int> b) {
        int n = a.size();
        for (int i = 0; i < n; ++i) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
};