.
2019-12-26 吴亲库里 库里的深夜食堂
给定包含红色，白色，蓝色并且总数为 n 的数组。使用原地排序使得相同颜色的紧邻在一起。按照红色，白色，蓝色的顺序排序。其中用 0 表示红，1 表示白，2 表示蓝。题目的本意是想让你在 O(n) 的时间复杂度以及 O(1) 的空间复杂度下完成。
这是一道经典题。也被称为荷兰国旗问题🇳🇱。一种超级巧妙的算法思路就是:设置三个变量(所以空间复杂度依然是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了，就是可以这么理解。
/**
* @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;
}
