关于算法:LeetCodeGolang-75-颜色分类

题目：

给定一个蕴含红色、红色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得雷同色彩的元素相邻，并依照红色、红色、蓝色顺序排列。

咱们应用整数 0、1 和 2 别离示意红色、红色和蓝色。

必须在不应用库的 sort 函数的状况下解决这个问题。

示例：

输出：nums = [2,0,2,1,1,0]
输入：[0,0,1,1,2,2]

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能够不应用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅应用常数空间的一趟扫描算法吗？

先贴代码：（GO 语言）

func sortColors(nums []int) {left, i, right := 0, 0, len(nums)-1
   // 不变量：left 之前（不蕴含 nums[left]）均为 0，right 之后（不蕴含 nums[right]）均为 2
   // all in [0,left) == 0
   // all in [left,i) == 1
   // all in (right,len) == 2
   for i <= right {if nums[i] == 0 {nums[left], nums[i] = nums[i], nums[left]
         left++
         i++
      } else if nums[i] == 2 {nums[right], nums[i] = nums[i], nums[right]
         right--
      } else {i++}
   }
}

咱们能够借鉴疾速排序的思维对问题进行剖析。首先设置循环不变量如下：

• [0,left) == 0，即 left 之前（不包含 nums[left]）不蕴含元素0 之外的元素。
• [left,i) == 1，即 left 和目前循环到的 i 之间不蕴含元素 1 之外的元素。
• (right,len) == 2，即 right 之后（不包含 nums[right]）不蕴含元素2 之外的元素。

算法解决步骤如下：

• 初始 left 设为 0，i 设为 0，right 设为 len-1，则为0 的区间是 [0,0)，不蕴含元素。为1 的区间是 [0,0)，不蕴含元素。为2 的区间是(len-1,len)，不蕴含元素。所以初始状态满足不变式要求。

• 接下来的循环中，依据 nums[i] 的值进行保护不变式的操作。分为以下三种状况

  • 当 nums[i] 为0时，替换 nums[i] 和nums[left]，并使 left 和i后移，满足不变式。
  • 当 nums[i] 为1时，后移i，满足不变式。
  • 当 nums[i] 为2时，替换 nums[i] 和nums[right]，并使 right 前移，满足不变式。留神替换后是 nums[right] 的值承受了本次循环的值判断，而替换后的 nums[i] 的值并没有承受值判断，所以不执行 i 的后移操作，须要在下一次循环中依据其值解决。
• 因为后两个区间中 i 和right均为开区间，若当 i == right 循环进行，则元素 nums[i] 也能够说是元素 nums[right] 没有通过分类解决，因而最终循环终止条件为i <= right，这样能力保障数组中的每个元素均被解决过，且最终三个区间均满足不变式，算法成立。

复杂度剖析：

• 工夫复杂度：O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(1)。咱们只须要常数的空间存储若干变量。