LeetCode 47.全排列 II

博主 918 2020-09-18

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

示例:

  • 输入: [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;
        }
    }
};