LeetCode 47. Permutations II题目解析-wowAC

Description

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

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

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

题目复述

给定一个数组,可能包含相同的元素,生成所有可能的排列。

题目解析

因为涉及到相同的元素,因此考虑使用字典序生成排列的方法,这种方法的基本思想是假设我们可以根据当前排列找出字典序大于当前排列的下一个排列,那么我们就可以重复的生成所有排列。对于当前排列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 4 4 3,那么j = 0,k = 3,交换P[j]、P[k]后得到3 4 4 1,翻转P[j+1 – 3]得到3 1 4 4。

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>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        do {
            res.push_back(nums);
        }while(next_permu(nums));
        return res;
    }
};

发表评论

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