LeetCode（75）：分类颜色

Medium！

题目描述：

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

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]

输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

解题思路：

这道题的本质还是一道排序的题，题目中给出提示说可以用计数排序，需要遍历数组两遍，那么先来看这种方法，因为数组中只有三个不同的元素，所以实现起来很容易。

- 首先遍历一遍原数组，分别记录0,1,2的个数
- 然后更新原数组，按个数分别赋上0，1，2

C++解法一：

 class Solution {

 public:

     void sortColors(int A[], int n) {

         int count[] = {}, idx = ;

         for (int i = ; i < n; ++i) ++count[A[i]];

         for (int i = ; i < ; ++i) {

             for (int j = ; j < count[i]; ++j) {

                 A[idx++] = i;

             }

         }

     }

 };

题目中还要让只遍历一次数组来求解，那么我需要用双指针来做，分别从原数组的首尾往中心移动。

- 定义red指针指向开头位置，blue指针指向末尾位置

- 从头开始遍历原数组，如果遇到0，则交换该值和red指针指向的值，并将red指针后移一位。若遇到2，则交换该值和blue指针指向的值，并将blue指针前移一位。若遇到1，则继续遍历。

C++解法二：

 class Solution {

 public:

     void sortColors(int A[], int n) {int red = , blue = n - ;

         for (int i = ; i <= blue; ++i) {

             if (A[i] == ) {

                 swap(A[i], A[red++]);

             } else if (A[i] == ) {

                 swap(A[i--], A[blue--]);

             }

         }

     }

 };

巴特西

LeetCode（75）：分类颜色

最新文章

热门文章