LeetCode 46.Permutations题目解析-wowAC

Description

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

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

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题目复述

给定一组互不相同的数的集合,返回所有可能的排列。

题目解析

1.暴力枚举法

为了枚举所有的排列,我们可以得到一棵排列树,如图1.11,因此我们只需要使用dfs(深度优先搜索)遍历一下整颗树即可。

class Solution {
public:
    /*
    used_num:已经使用了的数的个数
    used:标记哪些数使用了而哪些数没有使用
    nums:题目给定的数的集合
    now_permu:当前的排列
    res:用于记录答案
    */
    void dfs(int used_num, vector<int>& used, vector<int>& nums, vector<int>& now_permu, vector<vector<int>>& res) {
        if(used_num == nums.size()) {
            res.push_back(now_permu);
            return ;
        }
        
        for(int i=0; i<nums.size(); i++) {
            if(used[i] == 1) continue;
            used[i] = 1;
            now_permu.push_back(nums[i]);
            dfs(used_num+1, used, nums, now_permu, res);
            now_permu.pop_back();
            used[i] = 0;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> used(nums.size(), 0), now_permu;
        vector<vector<int>> res;
        dfs(0, used, nums, now_permu, res);
        return res;
    }
};

2.字典序生成排列法

这种方法的基本思想是假设我们可以根据当前排列找出字典序大于当前排列的下一个排列,那么我们就可以重复的生成所有排列。对于当前排列s = P[1 – n]这种方法的具体操作如下:

1:从右向左找到一个下标j使得P[j] < P[j+1],这意味着P[j+1]>=P[j+2]>=…>=P[n]

2:从P[j+1 – n]中大于P[j]的所有数中找出下标最大的数,记此小标为k,这个数也是大于P[j]的最小的那个数

3:交换P[j]和P[k]

4:翻转P[j+1 – n]所得排列即为下一个排列。

例如当前排列是1 2 4 3,那么j = 1,k = 3,交换P[j]、P[k]后得到1 3 4 2,翻转P[j+1 – 3]得到1 3 2 4。

字典序生成排列的方法还可以应用于有重复数字的排列中,而dfs暴力枚举在生成有重复数字的排列的时候会生成大量重复的排列,还需注意的是字典序生成排列的方法最初排列的字典序应该为最小,即从小到大排列。

class Solution {
public:

    bool next_permu(vector<int>& nums) {
        if(nums.size() == 0 || nums.size()==1) return false;
        int j, k;
        for(j = nums.size()-2; j>=0; j--)
            if(nums[j] < nums[j+1])
                break;
        if(j == -1) return false;  //没有下一个排列了
        
        for(k=nums.size()-1; k>j; k--)
            if(nums[k] > nums[j]) break;
        swap(nums[j], nums[k]);
        for(int i=j+1; i<=(j+1+nums.size()-1)/2; i++) {
            int rev_i = j+1+nums.size()-1-i;
            swap(nums[i], nums[rev_i]);
        }
        return true;
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        do {
            res.push_back(nums);
        }while(next_permu(nums));
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注