Leetcode: Permutations

柔情只为你懂 2022-08-07 15:53 197阅读 0赞

题目：  
Given a collection of 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], and [3,2,1].

思路分析：  
思路一：  
最容易想到的就是递归了！每次在num中拿出1个数字放在第一个，然后剩下的数字做一个全排列。  
C++参考代码：

class Solution
    {
    public:
        vector<vector<int> > permute(vector<int> &num)
        {
            int size = int(num.size());
            vector<vector<int>> result;//num全排列的结果
            if (1 == size)
            {
                result.push_back(num);
                return result;
            }
            vector<int> currentElement;//临时保存当前的num
            vector<vector<int>> remainingResult;//num除去一个元素以后剩下元素的全排列结果
            vector<int> currentResult;//保存当前num的每个全排列
            for (int i = 0; i < size; ++i)
            {
                currentElement = num;
                currentElement.erase(currentElement.begin() + i);//去掉第i个元素（从0开始）
                remainingResult = permute(currentElement);//后续元素的全排列
                int remainingResultSize = int(remainingResult.size());
                for (int j = 0; j < remainingResultSize; ++j)
                {
                    currentResult = remainingResult[j];
                    currentResult.insert(currentResult.begin(), num[i]);//在开始位置插入num[i]
                    result.push_back(currentResult);
                }
            }
            return result;
        }
    };

思路二：  
同样使用递归：每次循环交换第一个元素和后面元素的位置，然后第一个元素和后面元素的全排列依次加入结果数组中。比如：  
  
对于数组\[1,2,3\]  
1. 交换1和1的位置（其实第一次不用交换），生成\[2, 3\]的全排列\[2, 3\]和\[3, 2\]，然后把1加上去生成\[1, 2, 3\]和\[1, 3, 2\]。交换完以后换回来。  
2. 交换1和2的位置，生成\[1, 3\]的全排列\[1, 3\]和\[3, 1\]，然后把2加上去生成\[2, 1, 3\]和\[2, 3, 1\]。交换完以后换回来。  
3. 交换1和3的位置，生成\[2, 1\]的全排列\[2, 1\]和\[1, 2\]，然后把3加上去生成\[3, 2, 1\]和\[3, 1, 2\]。交换完以后换回来  
  
其实思路一和思路一有相似之处：都是选出一个元素，剩余元素做全排列。不同的是一：循环遍历给定数组进行计算；二通过交换第一个元素和后面元素的位置，结果为第一个元素+后面元素的全排列。  
C++参考代码：

class Solution {
    private:
        vector<vector<int>> result;
        int size;
        void permuate(vector<int> &num, int index)
        {
            if (index == size)
            {
                result.push_back(num);
                return;
            }
            for (int i = index; i < size; ++i)
            {
                swap(num[index], num[i]);//交换i和index元素
                permuate(num, index + 1);//计算除去index元素，后面元素的全排列
                swap(num[index], num[i]);//再换回来
            }
        }
    public:
        vector<vector<int> > permute(vector<int> &num)
        {
            size = int(num.size());
            permuate(num, 0);
            return result;
    
        }
    };

思路三：  
使用STL提供的next\_permutation函数，next\_permutation函数能够以字典序列的方式输出排列的结果，详见：[next\_permutation][next_permutation]。不过直接调用库函数貌似没有体现自己的思考与自己的算法！  
C++参考代码：

class Solution
    {
    public:
        vector<vector<int> > permute(vector<int> &num)
        {  
            vector<vector<int> > result;
            sort(num.begin(), num.end());//给num升序排序
            result.push_back(num);
            while (next_permutation(num.begin(), num.end()))
            {
                result.push_back(num);
            }
            return result; 
        }  
    };

[next_permutation]: http://www.cplusplus.com/reference/algorithm/next_permutation/