[leetcode] 47. Permutations II解題レポート

タイトルリンク:https://leetcode.com/problems/permutations-ii/
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] .
考え方:次の辞書の順序にルールがあることを求めます.例えば、1,2,3,4,5,6の6つの数の最初の辞書順は、1,2,3,4,5,6の増分配列であり、最後の配列は逆配列の6,5,4,3,2,1である.
栗を挙げる:6,3,5,4,2,1,この数の次の辞書の順序を探すには、次の手順に従います.
1.右から左に向かって右より小さい最初の数を見つける3
2.そしてこの数の右5から最後の3より大きい数を右に探す4
3.この2つの値を交換すると、配列は6,4,5,3,2,1になります.
4.次に、4の後の数をインクリメントシーケンスに並べ、その場で逆シーケンスにします.その後の配列は6,4,1,2,3,5になります.このシーケンスは、私たちが要求する次の辞書シーケンスです.
配列を昇順に並べ、完全に逆順になるまで次の辞書順を求めます.
コードは次のとおりです.

class Solution {
public:
    void findNext(vector<int>& nums)
    {
        int pos=nums.size()-1, pos2=0;
        while(pos > 0 && nums[pos-1] >= nums[pos])
            pos--;
        for(int i = pos; i< nums.size(); i++)//    nums[pos]       
            pos2 = nums[i]>nums[pos-1]?i:pos2;
        swap(nums[pos-1], nums[pos2]);
        reverse(nums.begin()+pos, nums.end());
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        int len = nums.size(), i = 0;
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        while(i < len)
        {
            result.push_back(nums);
            for(i = 1; i< len; i++)
                if(nums[i] > nums[i-1]) break;
            if(i >= len) break;//       
            findNext(nums);
        }
        return result;
    }
};