Skip to content

Latest commit

 

History

History
188 lines (178 loc) · 7.49 KB

46. Permutations.md

File metadata and controls

188 lines (178 loc) · 7.49 KB
Raw

46. Permutations

思路

返回一个数组的所有排列，数组中元素没有重复。

思路一、Next Permutation

如果做了31. Next Permutation的话那这题就没什么问题了。稍有不同的是此题的数组元素没有重复而31题中可能重复。
所以此题可以使用STL中现成的next_permutation函数：

bool next_permutation (first, last)返回的是bool型，如果已经是最后一个排列了则返回false并将数组变成第一个排列(即按照从小到大排好序)；否则返回true并将数组变成下一个排列。 此外还可以传入comp参数: next_permutation (first, last, comp)这样就可以自定义数组的大小规则。

另外也可手动实现这个函数，参见我的31题题解。
亲测使用STL中的要比手动实现慢很多。

思路二、DFS（常规思路，务必掌握）

根据经验，像这种要求出所有结果的集合，常规思路DFS递归求解。这里有两种DFS思路。

普通DFS

用一个数组pmt记录此时的排列，还需要用到一个visited数组来标记某个数字是否访问过，然后每个DFS递归函数的for循环应从头开始（注意77. Combinations题解中不是从头开始的，注意区别）。当pmt和nums一样长时说明pmt是一个全排列，此时应将pmt存放进结果数组res里并跳出当前递归。注意这里for循环应从头开始是因为这是求全排列（而不像77题那样求组合），每个位置都可能放任意一个数字，这样会有个问题，数字有可能被重复使用，由于全排列是不能重复使用数字的，所以我们需要用一个visited数组来标记某个数字是否使用过。

swap DFS

此题可以使用的另一种DFS是基于这样一种思路：每次交换num里面的两个数字，经过递归可以生成所有的排列情况。即第一次递归时，nums的第1个数字可以选择分别和第1、2...、n个数字交换；在第一次递归的某种情况的基础上，第二次递归可以让nums的第2个数字分别和第2、3...、n个数字进行交换......，我们利用一个参数start记录当前所在的递归层数（从0开始），当start = n时当前nums中就是一个之前未出现过的全排列，将其送入结果数组res中并跳出当前递归，这样经过n次递归就可以获得所有全排列。

思路三、

最后再来看一种巧妙的方法：

  • 当n=1时，数组中只有一个数a1，其全排列只有一种，即为a1；
  • 当n=2时，数组中此时有a1a2，其全排列有两种即a1a2和a2a1。此时我们考虑和n=1时的关系，我们发现，其实就是在a1的前后两个位置分别加入了a2；
  • 当n=3时，数组中有a1a2a3，此时全排列有六种，分别为a1a2a3、a1a3a2、a2a1a3、a2a3a1、a3a1a2和a3a2a1。对比n=2发现，实际上是在a1a2和a2a1的基础上在不同的位置上加入a3而得到的。

针对上述思路可以写出递归和迭代两种代码。

C++

思路一、Next Permutation

使用STL中的next_permutation

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        if(nums.empty()) return res;
        sort(nums.begin(), nums.end()); // 先排序
        res.push_back(nums);
        while(next_permutation(nums.begin(), nums.end())) res.push_back(nums);
        return res;
    }
};

手动实现(亲测更快)

class Solution {
private:
    bool my_next_permute(vector<int>& nums){
        int len = nums.size();
        int i = len - 1;
        while(i > 0 && nums[i] < nums[i - 1]) i--;
        if(i == 0) return false;
        
        int mid, low = i, high = len - 1;
        while(low <= high){ // 二分查找
            mid = low + (high - low) / 2;
            if(nums[mid] < nums[i - 1]) high = mid - 1;
            else low = mid + 1;
        }
        
        // int high = len - 1;
        // while(nums[i - 1] > nums[high]) high--;
        
        swap(nums[i - 1], nums[high]);
        reverse(nums.begin() + i, nums.end());
        return true;
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        if(nums.empty()) return res;
        sort(nums.begin(), nums.end()); // 先排序
        res.push_back(nums);
        while(my_next_permute(nums)) res.push_back(nums);
        return res;
    }
};

思路二

普通DFS

class Solution {
private:
    void DFS(vector<vector<int>>&res, vector<int>&pmt, vector<int>&visited, const vector<int> &nums){
        int n = nums.size();
        if(n == pmt.size()){
            res.push_back(pmt);
            return;
        }
        for(int i = 0; i < n; i++){
            if(visited[i]) continue;
            visited[i] = 1;
            pmt.push_back(nums[i]);
            DFS(res, pmt, visited, nums);
            visited[i] = 0;
            pmt.pop_back();   
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        vector<int>pmt;
        vector<int>visited(nums.size(), 0);
        DFS(res, pmt, visited, nums);
        return res;
    }
};

swap DFS

class Solution {
private:
    void DFS_swap(vector<vector<int>>&res, vector<int> &nums, const int start){
        int n = nums.size();
        if(start >= n){
            res.push_back(nums);
            return;
        }
        for(int i = start; i < n; i++){
            swap(nums[start], nums[i]);
            DFS_swap(res, nums, start + 1);
            swap(nums[start], nums[i]);  
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        DFS_swap(res, nums, 0);
        return res;
    }
};

思路三

递归

class Solution {
private:
    void helper(vector<vector<int>>&res, const int curr_n, const vector<int> &nums){
        if(curr_n == nums.size()) return;
        if(curr_n == 0) res.push_back(vector<int>(1, nums[0]));
        else{
            int res_size = res.size();
            for(int i = 0; i < curr_n; i++){ // curr_n为复制次数
                for(int j = 0; j < res_size; j++){
                    auto pmt = res[j];
                    pmt.insert(pmt.begin() + i, nums[curr_n]);
                    res.push_back(pmt);
                }
            }
            for(int i = 0; i < res_size; i++)
                res[i].push_back(nums[curr_n]);
        }
        helper(res, curr_n + 1, nums);
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        helper(res, 0, nums);
        return res;
    }
};

迭代

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        res.push_back(vector<int>(1, nums[0]));
        int curr_n = 1, n = nums.size();
        while(curr_n < n){
            int res_size = res.size();
            for(int i = 0; i < curr_n; i++) // curr_n为复制次数
                for(int j = 0; j < res_size; j++){
                    auto pmt = res[j];
                    pmt.insert(pmt.begin() + i, nums[curr_n]);
                    res.push_back(pmt);
                }
            for(int i = 0; i < res_size; i++)
                res[i].push_back(nums[curr_n]);
            curr_n++;
        }
        return res;
    }
};