首页 > 代码库 > 【LeetCode】046. Permutations

【LeetCode】046. Permutations

2024-09-17 11:18:44   216人阅读

题目：

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]
]

　　

题解：

　　之前解过Next Permutation，故这个题可以重复调用nextPermutation函数产生全排列

Solution 1 ()

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        for(int i=n-2; i>=0; --i) {
            if(nums[i]>=nums[i+1]) continue;
            int j = n-1;
            for(; j>i; --j) {
                if(nums[j]>nums[i]) break;
            }
            swap(nums[i], nums[j]);
            reverse(nums.begin()+i+1, nums.end());
            return;            
        }
        reverse(nums.begin(), nums.end());
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> vv;
        vector<int> v = nums;
        vv.push_back(v);
        nextPermutation(v);
        while(v != nums) {
            vv.push_back(v);
            nextPermutation(v);
        }
        return vv;
    }
};

　　其实这个问题很容易想到递归的解法，取第一个数后对剩下的元素进行全排列

Solution 2 ()

 

【LeetCode】046. Permutations


联系
我们