75.md

:pencil2:基础刷题之(75. Sort Colors)

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

:pencil2:描述

给定包含红色，白色，蓝色并且总数为 n 的数组。使用原地排序使得相同颜色的紧邻在一起。按照红色，白色，蓝色的顺序排序。其中用 0 表示红，1 表示白，2 表示蓝。题目的本意是想让你在 O(n) 的时间复杂度以及 O(1) 的空间复杂度下完成。

---

:pencil2:题目实例

​

---

:pencil2:题目分析

这是一道经典题。也被称为荷兰国旗问题🇳🇱。一种超级巧妙的算法思路就是:设置三个变量(所以空间复杂度依然是O(1)，并不是说定义了三个变量空间复杂度就是O(n)了，这点我想你们应该明白)。变量 $p0 用来表示存储 0 的最右边界，$p2 表示 2 的最左边界，$curr 表示当前遍历的位置。初始化的时候$p0=0 表示从开头开始，$p2 等于最后的位置（解释起来很简单 因为最开头的最后肯定是 0，最右边的最后肯定是 2)，然后遍历数组，只要是等于 0 的，就把当前位置的值(也就是 0)和$p0 位置的值互换 并且 $p0 向右移动一位。等于2 就把当前位置的值（也就是 2)和$p2 互换，并且 $p2向左移动一位。否则的话移动 curr 即可。这样的话 0 一直往右边填充，2 一直向左边挤压，中间剩下的就是1了，就是可以这么理解。

:pencil2:最终实现代码

      /**
         * @param Integer[] $nums
         * @return NULL
         */
        function sortColors(&$nums)
        {
            $curr = 0;
            $p0 = 0;
            $p2 = count($nums) - 1;
            while ($curr <= $p2) {
                $temp = $nums[$curr];
                if ($nums[$curr] == 0) {
                    $nums[$curr] = $nums[$p0];
                    $nums[$p0] = $temp;
                    $p0++;
                    $curr++;
                } elseif ($nums[$curr] == 2) {
                    $nums[$curr] = $nums[$p2];
                    $nums[$p2] = $temp;
                    $p2--;
                } else {
                    $curr++;
                }
            }
            return $nums;
        } 

---

联系

​