双指针练习---力扣第75题

题目：颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列，此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

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

示例1: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 示例2： 输入：[2,0] 输出：[0,2]

思路：

这个题用排序当然是可以写出来的，这里不做讨论，本篇分享将使用双指针通过一次遍历来解决这个问题。 双指针： 这个题思路就是把所有的2往数组右边放，所以建立两个指针，p0,p1同时指向数组的第一个元素，当遍历时出现0或1，p0和p1指针才开始移动。具体移动方法：当遍历数组出现1时，与p1指向的值进行交换，然后p1++；当遍历数组出现0时，与p0指向的值进行交换，此时需要注意，如果之前p1指针已经移动过，那么p0指向的值就是0，那么当p0发生交换时，就会把1交换出去，这个时候，需要再利用一次p1把1重新交换回来。但是无论如何，在交换p0之后，p0和p1都应该向下移动一次，因为0只要保持在左边就好了，于是就把两个指针都往下移动一次。

代码：

public void sortColors(int[] nums) { int n = nums.length; int p0 = 0, p1 = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 1) { int temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; ++p1; } else if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[p0]; nums[p0] = temp; if (p0 < p1) { temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; } ++p0; ++p1; } } }

时间复杂度：

因为只遍历了一次数组，所以时间复杂度为O(n)，其中n为数组长度。 如果有不对或不清楚的地方请批评指正。