31.md

✏️Leetcode之PHP版题目解析（31. Next Permutation）

2019-12-23 吴亲库里 库里的深夜食堂

---

✏️描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数列重新排列成最小的排列。这道题说真的好难理解啊(可能是我理解能力太差了)。

---

✏️题目实例

​ ****

✏️题目分析

递归这是一道有关于字典序排序的算法。可以先去了解一下什么是字典序。我也是去查了资料。所以我这里举一个例子说明答案是咋么出来的。假设给定一下数字排列

[1,2,10,5,3,1] 
下一个排列是
[1,3,1,2,5,10] 即答案

那么结果是如何出来的呢。我们通过原数组，从右往左看，数值是递增的，直到索引1(值等于2)这个位置的时候，开始比10小，记住这个位置 A，然后从右往左找到第一个比A位置大的数(是3)，交换这两个位置的值，然后把 A 位置之后的数左右转置，即可。

✏️代码实现

           /**
            * @param Integer[] $nums
            * @return NULL
            */
           function nextPermutation(&$nums)
          {
               $i = count($nums) - 2;
               //先确定位置A
               while ($i >= 0 && $nums[$i + 1] <= $nums[$i]) {
                   $i--;
               }
               if ($i >= 0) {
                   $j = count($nums) - 1;
                   //如果没有比 A 大的继续寻找
                   while ($j >= 0 && $nums[$j] <= $nums[$i]) {
                       $j--;
                   }
                   //找到了交换位置
                   $this->swap($nums, $i, $j);
               }
       
               // A 之后的数转置
               $this->reverse($nums, $i + 1);
               return $nums;
           }
       
           function swap(&$nums, $i, $j)
       {
               $temp = $nums[$i];
               $nums[$i] = $nums[$j];
               $nums[$j] = $temp;
           }
       
           function reverse(&$nums, $i)
       {
               $start = $i;
               $end = count($nums) - 1;
               while ($start < $end) {
                   $this->swap($nums, $start, $end);
                   $start++;
                   $end--;
               }
       
           }

---

联系

​