首页 > itarticle > [leetcode]sort colors

[leetcode]sort colors

admin 11月 11, 2020 0

题目描述

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

代码一

public class Solution {
    
    //维护两个索引指针left、和right，left初始为0，right初始为nums.length-1
    //然后遍历数组，遇到0时交换到left位置，遇到2时交换到right位置
    public void (int[] nums) {
        if(nums == null || nums.length == 0) return;
        int left = 0, right = nums.length-1;
        
        int i = 0;
        
        //循环终止条件为i<=right
        while(i <= right){
            if(nums[i] == 0){
                int temp = nums[left];
                nums[left] = nums[i];
                nums[i] = temp;
                left++;
                i++;
            }else if(nums[i] == 1){
                i++;
            }else{
                int temp = nums[right];
                nums[right] = nums[i];
                nums[i] = temp;
                //交换过来的nums[right]有可能是0，i不能++
                right--;
            }
        }
    }
}

代码二