颜色分类(Java)

你的名字 2024-04-06 12:36 29阅读 0赞

### 75. 颜色分类 ###

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

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

> 必须在不使用库的sort函数的情况下解决这个问题。

##### 示例 1： #####

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

##### 示例 2： #####

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

##### 提示： #####

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

#### 思路：（双指针） ####

1.  因为0肯定在前面，2肯定在数组的后面，所以只需设置两个指针zero,two，分别指向数组的头部和尾部；
2.  如果遇到2，则和尾部指针two指向的位置交换，然后two-1；
3.  如果遇到0，则和头部指针zero指向的位置交换，然后zero+1；
4.  如果遇到1，则不需要管

##### 代码： #####

public class color_sort {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [] nums = {
        2,0,1};
    		sortColors(nums);
    		for(int k=0; k<nums.length; k++) {
        
    			 System.out.print(nums[k]);
    		}
    	}
    	 public static void sortColors(int[] nums) {
        
    		 int two = nums.length - 1;
    		 int zero = 0;//指向1的前一位
    		 int i = 0;
    		 while(i <= two) {
        
    			if(nums[i] == 2) {
        //如果是2直接和最后一个交换
    				swap(nums,i,two--);
    			}else if(nums[i] == 0) {
        //只要是0就和zero交换
    				swap(nums,zero++,i++);
    			}else {
        
    				i++;
    			}	 
    		 }
    	 }
    	 public static void swap(int[] nums, int i, int j) {
        
    		 int t = nums[i];
    		 nums[i] = nums[j];
    		 nums[j] = t;
    	 }
    }

##### 复杂度分析: #####

*  时间复杂度：O(n)，其中 n 是数组 nums 的长度。
 *  空间复杂度：O(1)。

##### 进阶： #####

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

来源：[力扣（LeetCode）][LeetCode]

注：仅供学习参考！

[LeetCode]: https://leetcode.cn/problems/sort-colors