L75 Sort Color

Problem

Given an array with n objects colored red, white or blue, sort them in-place 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.

Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]

Solution

Since we have three kinds of colors in total, so we just need to swap the position of zero and two. If we find it is zero, we just need to swap the position with the first index of the numbers. If it is two, swap it with the last index of the numbers.

To swap the numbers, we call the swap function.

TC:O(n), SC: O(1)

public void sortColor(int[] nums){
    if(nums == null || nums.length == 0) return;
    int zero = 0, two = nums.length - 1;
    for(int i = 0; i <= two; i++){
        if(nums[i] == 0) swap(nums, zero++, i);
        else if(nums[i] == 2) swap(nums, two--, i);
    }
}
private void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}