09
18

发表于 • • 被 61 人看爆

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

  • 输入: [1,1,2]
  • 输出:
    [
    [1,1,2],
    [1,2,1],
    [2,1,1]
    ]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
这道题的关键在给定的序列可以包含重复的数字，不注意这一点可能会求得大量重复的全排列：重复数字填入顺序不同得到的排列是相同的全排列，不是不同的全排列。

eg:上面示例中有两个1，一个2，为了区分两个1 我们记作输入[1(1), 1(2), 2]
排列 [1(1), 1(2), 2]和排列[1(2), 1(1), 2]实际上是相同的排列
为了区分这类重复的全排列，我们固定重复数字的填入顺序：

  • 首先对输入序列排序，使相同的数字在序列中连续
  • 固定重复数字的填入顺序，即1(1)在所有1中一定是最先填入全排列中的数字，1(2)一定是所有1中第二排入全排列中的数字，依次类推...
  • 要想达到这一点：我们首先用一个数组visit[]表示第i个位置的数字是否填入了全排列中，其次设定条件，只有当重复数字的前一个数字填入了排列中，这个数字才可以填入全排列。假定当前判断是否要填入的数字为nums[i]，只有当visit[i-1]==true && nums[i] == nums[i-1]时，重复数字才可以填入，也就是下面代码中visit[i-1]==false && nums[i] == nums[i-1]时，跳过当前重复数字nums[i]，不允许填入

下面给出代码：

class Solution {
private:
    vector<bool> visit;
    vector<vector<int> > ans;
public:
    /**
     给定一个可包含重复数字的序列，返回所有不重复的全排列
     **/
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        visit.resize(nums.size());
        sort(nums.begin(), nums.end());
        vector<int> tmp;
        getNextNum(nums, tmp, 0);
        return ans;
    }
    
    /**
     index 表示将要填的位置 从0~size-1的位置
     **/
    void getNextNum(vector<int>& nums, vector<int>& temp, int index){
        if (index == nums.size()) {// 填完了所有位置，获得一个全排列
            ans.push_back(temp);
//            cout << "获得一个全排列" << endl;
            return;
        }
        
        // index < n 还需要向当前index位置填入一个数字
        for (int i = 0; i < nums.size(); ++i) {
            // 如果nums[i] 填过了 或者 nums[i]不是当前连续重复数字的第一个位置
            if (visit[i] || (i > 0 && !visit[i-1] && nums[i] == nums[i-1] )) {
                continue;
            }
            // 填入当前nums[i]
//            cout << "填入数字" << nums[i] << endl;
            visit[i] = true;
            temp.push_back(nums[i]);
            // 获取下一个位置的数字
            getNextNum(nums, temp, index+1);
            temp.pop_back();
            visit[i] = false;
        }
    }
};
分享到：