学步园

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],
and [2,1,1].

算法一，

算法思路：

利用另一个问题Next Permutation的解法。

先进行排序，组成一个从小大到的排列。

每一次循环，求出一个值更大的排列。

直到溢出，即回归到初始状态。

在leetcode上实际执行时间为38ms。

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> >ans;
        ans.push_back(num);
        if (num.size() < 2)
                return ans;

        while (nextLargePermutation(num)) 
                ans.push_back(num);

        return ans;
    }

    bool nextLargePermutation(vector<int> &num) {
        int i = num.size() - 2;
        while (i>=0 && num[i]>=num[i+1]) i--;
        if (i < 0) return false;

        int j = num.size() - 1;
        while (num[j] <= num[i]) j--;

        swap(num[i], num[j]);
        reverse(num.begin()+i+1, num.end());
        return true;
    }
};

算法二，利用unordered_map却重

此算法在leetcode上的实际执行时间为38ms。和算法一差不多。

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        sort(num.begin(), num.end());
        vector<vector<int> >ans;
        helper(ans, 0, num);
        return ans;
    }

    void helper(vector<vector<int> > &ans, size_t start, vector<int> &num) {
        if (start+1 == num.size())
                return ans.push_back(num);

        unordered_map<int, int> map;
        for (size_t i=start; i<num.size(); i++) {
                if (++map[num[i]] > 1)
                        continue;

                swap(num[start], num[i]);
                helper(ans, start+1, num);
                swap(num[start], num[i]);
        }
    }
};