Permutation

发表于 | 分类于

全排列专题

题目描述：

全排列是面试中经常出现的题目，所以这边有需要做一下关于这一类的专题。首先我们从最简单的题目开始。给定一个数组，根据全排列的规律，找到当前排列的下一个全排列。

我们已知对于1，2，3排列而言，它的全排列依次如下：
1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1

例子：

以数组[1,3,8,7,6,5,4,2]为例子，我们首先找到第一次出现降序的位置3；再找到第一次比3大的位置4；交换二者的数据得到[1,4,8,7,6,5,3,2]；再将4后面的数组逆序即可得到[1,4,2,3,5,6,7,8]

解题思路：

初看例子我们还无法看出前后排列之间的关系。通过网上资料查询我们可以知道，从当前排列得到下一个排列的算法：

  • 首先我们从数组的末端开始遍历数组，直到第一次遇到num[i] < num[i + 1]的地方
  • 然后我们从数组末尾开始找到第一次出现比num[i]大的数的位置num[j]
  • 交换num[i]和num[j]
  • 将i后面的数组逆序后即可以得到当前排列的下一个排列

代码如下：

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:
    void nextPermutation(vector<int>& nums) {
        int k = -1;
        for (int i = nums.size() - 2; i >= 0; i--){
            if (nums[i] < nums[i + 1]){
                k = i;
                break;
            }
        }
        //先找到第一次降序的位置k，如果k是-1说明整个数组降序即为最后一个全排列，直接逆序全数组得到第一个全排列
        if (k == - 1){
            reverse(nums.begin(), nums.end());
            return;
        }
        int l = -1;
        for (int i = nums.size() - 1; i >= 0; i--){
            if (nums[i] > nums[k]){
                l = i;
                break;
            }
        }
        //从数组末尾开始找到第一次大于待交换数字的位置
        swap(nums[l], nums[k]);
        //交换二者的数据
        reverse(nums.begin() + k + 1, nums.end());
        //逆序从降序位置后开始到数组末尾的数字
        
        
    }
};

题目描述2

在上述题目中，我们没有考虑到关于在数组中可能存在重复数字的情况。现在给定一个数组，其中可能包含重复数字，要求返回所有不重复的可能的排列结果。上文中所述的方法恰好排除了这种可能重复出现的情况。所以基本还是沿用上一题的思路来解决这个问题。

代码如下：

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());//先进行排序
        vector<vector<int>> res;//用于保存结果
        res.push_back(nums);//先将当前结果保存
        
        while(1){
            int k = -1;
            for (int i = nums.size() - 2; i >= 0; i--){
                if (nums[i] < nums[i + 1]){
                    k = i;
                    break;
                }
            }//找到降序
            if (k == -1)break;
            int l = -1;
            for (int j = nums.size() - 1; j > k; j--){
                if (nums[j] > nums[k]){
                    l = j;
                    break;
                }
            }//找到小于待交换的位置
            swap(nums[k], nums[l]);
            reverse(nums.begin() + k + 1, nums.end());
            res.push_back(nums);
        }
        return res;
    }
};

题目描述3：

在以上的解题过程中用的都是非递归的方法实现，现在要求使用递归的方式实现找到某个数组的全排列。主要的思路是用begin来标记当前要确定的排列位置，然后在从begin到数组末尾的各个数和begin进行交换得到不同的可能排列，而后进行下一个位置的寻找。遍历的停止条件是当前遍历位置大于数组长度的时候。需要注意的是，我们在遍历后需要进行一步回溯。比如在找到[1,3,2]后我们需要交换3和2变回[1,2,3]，便于下一步进行得到[2,1,3]结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        permutation(nums, 0, ans);
        return ans;
    }
    void permutation(vector<int>&nums, int begin, vector<vector<int>>& ans){
        if (begin >= nums.size()){
            ans.push_back(nums);
            return;
        }
        //如果当前遍历的位置到达数组的末尾，将数组保存即可
        for (int i = begin; i < nums.size(); i++){
            swap(nums[i], nums[begin]);
            //与当前遍历位置的各个数进行交换，然后进入下一层递归
            permutation(nums, begin+1, ans);
            swap(nums[i], nums[begin]);
            //需要回溯一步
        }
    }
};

题目描述4

在使用递归方法中，上述的方法无法解决出现重复数字的情况。比如[1,1,2]。因为在begin=0的情况中，i=0,1,2；而对于i=0得到[1,1,2]和i=1得到[1,1,2]得到的情况相同，后序的全排列重复。所以我们需要其他的方法来解决这个问题。其中之一就是哈希表。主要的思路是:我们用哈希表来记录数组中出现数字的次数，用vec来保存当前得到的全排列；每次从哈希表中找到一个数将其push到vec中，而哈希表中对应的出现个数减1；然后进入下一层递归即可。需要注意的是：我们每次push完一个数递归结束后，需要将这个数pop进行回溯；另外需要对哈希表中数字出现的个数进行增加和减少操作。

代码如下：

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
32
33
34
35
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;//保存结果
        map<int, int> hash;//记录个数
        vector<int>vec;//保存当前排列
        for (int i = 0; i < nums.size(); i++){
            hash[nums[i]]++;
        }//生成哈希表
        permutation(ans, vec, hash, nums.size());
        //递归找到全排列
        return ans;
        
    }
    void permutation(vector<vector<int>>& ans, vector<int>& vec, map<int,int>& hash, int end){
        if (end <= 0){
            ans.push_back(vec);
            return;
            //如果已经得到符合条件的全排列
        }
        for (auto &it: hash){
            if (it.second <= 0) continue;
            //如果当前元素已被使用完，查找下一个元素
            vec.push_back(it.first);
            //将当前元素导入保存
            it.second--;//对应元素个数减少
            permutation(ans, vec, hash, end - 1);
            //进行下一轮递归调用
            it.second++;
            //调用完记得恢复哈希表
            vec.pop_back();
            //恢复记录的排列
        }
    }
};