Skip to content

Latest commit

 

History

History
59 lines (49 loc) · 2.3 KB

47.md

File metadata and controls

59 lines (49 loc) · 2.3 KB

✏️Leetcode之PHP版题目解析（47. Permutations II)

2019-06-11 吴亲库里 库里的深夜食堂

✏️描述

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

✏️题目实例

​ ****

✏️题目分析

为了避免当次排列中数被重复使用，我们还是使用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;
               }
           }

联系

​