长春专业企业网站建设价格/百度竞价代理公司

题目

颜色分类
本题是经典的「荷兰国旗问题」，由计算机科学家 Edsger W. Dijkstra 首先提出。

思路一

• 使用双指针法。将数组划分为3个区间，即存储0的区间，存储1的区间，存储2的区间。
• 左指针从左到右移动，用于记录元素0的右边界。右指针从右向左移动，用于记录元素2的左边界。边界区间为左闭右开。
• 该方法类似于快排的partition过程，其中pivot设置为1。一次遍历，遇到0移动到左边，遇到2移动到右边，中间自然为1了。

代码

class Solution {public void sortColors(int[] nums) {// 左闭右开区间// 记录元素0的区间[0, one) = 0// 记录元素1的区间[one, i) = 1// 记录元素2的区间[two, nums.length) = 2// 将one初始化为0，保证[0, one)为空int one = 0;// 将two初始化为nums.length，保证[two, nums.length)为空int two = nums.length;// 将i初始化为0，保证[one, i)为空int i = 0;while(i < two){ // i>=two时终止，已经到达2的区间 if(nums[i] == 0){swap(nums, i, one);// 交换结束后，one指向0,i指向0或1one++; // one的位置不包括0，所以one需要+1// i>=one,因为2被交换到后面区间了,0被交换到前面区间了，因为[0,i]区间的元素只能是0或1i++; // i指向0或1，可以+1} else if(nums[i] == 2){--two; // 交换后，two的位置包括2，所以交换前需要-1swap(nums, i, two);//i++; // i为啥不要+1?因为从后面交换过来的nums[two]位置的元素不确定，需要继续判断} else{++i; // i的位置不包括1，所以nums[i]=1时需要+1}}}private void swap(int[] nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

思路二

• 单指针法。
• 第一次遍历，用于将0移动到左边。第二次遍历，用于将1移动到中间。2次遍历，2自然就被交换在最右边去了。

class Solution {public void sortColors(int[] nums) {int len = nums.length;int idx = 0;// 先把0移动到前面for(int i = idx; i < len; ++i){if(nums[i] == 0){swap(nums, i, idx++);}}// 把1移动到中间for(int i = idx; i < len; ++i){if(nums[i] == 1){swap(nums, i, idx++);}}}private void swap(int[] nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

思路三

• 第一次遍历统计每个元素的个数。第二次遍历利用个数进行填充元素。

class Solution {public void sortColors(int[] nums) {int count0 = 0;int count1 = 0;int count2 = 0;for(int i = 0; i < nums.length; ++i){if(nums[i] == 0){count0++;} else if(nums[i] == 1){count1++;} else{count2++;}}System.out.println(count0 + "," + count1 + "," + count2);int idx = 0;while(idx < nums.length){if(idx < count0){nums[idx++] = 0;} else if(idx < count0 + count1){nums[idx++] = 1;} else{nums[idx++] = 2;}}}
}