BM56 有重复项数字的全排列

2022-07-07  本文已影响0人  help_youself
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        std::sort(num.begin(),num.end());
        vector<vector<int> > res;
        int n=num.size();
        std::vector<int> path;
        std::vector<bool> visit(n,0);
        if(0!=n){
            conv(num,res,path,visit);
        }
        return res;
    }
    void conv(std::vector<int>&num,std::vector<std::vector<int>>& res,
              std::vector<int>&path,std::vector<bool>& visit){
        if(path.size()==num.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<num.size();i++){
            if(visit[i]) continue;
            if(i&&(num[i]==num[i-1])&&!visit[i-1]){
                continue;
            }
            visit[i]=true;
            path.push_back(num[i]);
            conv(num,res,path,visit);
            visit[i]=false;
            path.pop_back();

        }
    }

};
int main(){
    std::vector<int> data={1,1,3};
    Solution so;
    vector<vector<int> > ret=so.permuteUnique(data);
    int n=ret.size();
    for(int i=0;i<n;i++){
        int l=ret[i].size();
        for(int j=0;j<l;j++){
            std::cout<<ret[i].at(j)<<" ";
        }
        std::cout<<std::endl;
    }
    return 0;
}

 这里实现的代码,基本上是从博客[1]中抄袭的。这里主要解释下下面if语句中的判断条件是怎么起到筛选的作用的(筛除重复的组合)。尤其是!visit[i-1]的条件有点难以理解。

 if(i&&(num[i]==num[i-1])&&!visit[i-1]){
        continue;
 }

 假设测试序列为data={1,1,3},索引序号i为0,1,2。索引序号i的全排列为:

索引序号排列i,j,k 对应值data[i], data[j], data[k] if满足,执行continue
0,1,2 1,1,3 no
0,2,1 1,3,1 no
1,0,2 1,1,3 yes
1,2,0 1,3,1 yes
2,0,1 3,1,1 no
2,1,0 3,1,1 yes

 在执行for循环的过程中,没有被if条件过滤的数值组合,被存储到res.push_back(path)。针对data[i], data[j], data[k]序列重复的场景,可以观察if条件是否滤除的规律:

重复值对应索引序号按照升序排列的,数字排列留存。否则,就会被if条件滤除,执行continue.

 由于data[0]=data[1],索引序号(0,1,2)和索引序号(1,0,2)对应的值排列是相同的。索引序号(0,1,2)对应的排列,可以留下,而(1,0,2)对应的排列需要筛除。需要筛除的排列data[1], data[0], data[2],序号1在前,0在后面,可以认为是乱序的。
 在for循环中,通过visit[i]标记节点num[i]是否访问。当num[i]==num[i-1],说明数据重复,!visit[i-1]说明i-1对应的节点未被访问,假设continue语句不存在,则最终形成的序列B为:...data[i].....data[i-1]...。通过交换data[i]和data[i-1],可以得到序列A:...data[i-1].....data[i]...。
序列A和序列B是等价的。B序列对应的重复值的索引位置,是按照升序排列的。而if中的判定条件,就可以筛除序列A。

Reference:
[1]全排列(有重复项数字和无重复数字)

上一篇 下一篇

猜你喜欢

热点阅读