Leetcode基础刷题之PHP解析(47. Permutations II)

2019-6-11 期二 

递归第6天

Leetcode基础刷题之PHP解析(46. Permutations)

6ca6e36b601dcad0d8252aba9b3cf085.png


全排列第二版,这一版是给定数组中可能会出现相同的值,但是在结果中不能出现重复的排列。


为了避免当次排列中数被重复使用,我们还是使用visited标记,因为可能出现相同的值,但是又不能出现相同的排列,这里先把数组进行排序,然后递归中再设置一个条件,当前的数和他上一个数相等并且上一个数visited等于0的情况下说明此次已经是重复排列,退出。visited等于0并不是说前一个还没有被标记访问过,而是由于递归结束之后把当次排列当前下标visited重置为0。每一轮结束都需要重置为0,代表新一轮的排列。

   /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permuteUnique($nums) {
        sort($nums);
        $res=[];
        $out=[];
        $visitied=[];
        $this->helper($nums,0,$visitied,$out,$res);
        return $res;
    }
    
    function helper($nums,$index,&$visitied,&$out,&$res)
    {
        if($index==count($nums)){
            array_push($res,$out);
            return ;
        }
        for($j=0;$j<count($nums);$j++){
            if($visitied[$j]==1) continue;
            if($j>0 && $nums[$j]==$nums[$j-1] && $visitied[$j-1]==0) continue;
            $visitied[$j]=1;
            array_push($out,$nums[$j]);
            $this->helper($nums,$index+1,$visitied,$out,$res);
            array_pop($out);
             $visitied[$j]=0;
        }
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php

吴亲库里 has written 100 articles

情绪只是对自己无能的愤怒

积分:4877 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?