算法题之颜色分类问题(O(n)时间复杂度)

算法题之颜色分类问题(O(n)时间复杂度)

题目描述

思路分析

思路一图解

思路2图解

代码实现

//思路2:双指针操作 public void sortColors(int[] nums) { //定义两个指针:left指向数组起始索引,right指向数组末尾索引 int left = 0; int right = nums.length - 1; //for循环遍历nums数组 for (int i = 0; i < nums.length; i++) { //将数值为2的尽数移动到right指针处,并将right指针前移,若移动后,nums[i]仍然为2,则已经向后移动 while (i <= right && nums[i] == 2) { int temp = nums[i]; nums[i] = nums[right]; nums[right] = temp; right--; } //若数值为0,则将其移动到left指针位置处,并将left指针后移 if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[left]; nums[left] = temp; left++; } } } //思路1:单指针操作 public void sortColors02(int[] nums) { int p = 0; //将0值的位置进行分类排序 for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) { //将其与p指针交换位置 int temp = nums[i]; nums[i] = nums[p]; nums[p] = temp; p++; } } //将1值的位置再进行分类排序:此时从p位置开始遍历 for (int i = p; i < nums.length; i++) { if (nums[i] == 1) { int temp = nums[i]; nums[i] = nums[p]; nums[p] = temp; p++; } } }