[LeetCode] 75. Sort Colors

Problem

Given an array nums 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.

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

You must solve this problem without using the library’s sort function.

Example 1:

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

Example 2:

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

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

---

Solution

class Solution {
    public void sortColors(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1; j++)
                if (nums[j] == 2) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
            }
            for (int j = nums.length - 1; 0 < j; j--)
                if (nums[j] == 0) {
                    int tmp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = tmp;
            }
        }
    }
}

Explanation

• 배열 nums에서는 3종류의 요소인 0, 1, 2가 나타나는데, 0을 배열의 앞쪽으로 모으고, 2를 배열의 뒤쪽으로 모으면 0, 1, 2를 각각 분리할 수 있다.
• 배열 nums에서 2를 배열의 뒤쪽으로 모으기 위해 for 반복문을 중첩하여 작성한다.
• 마찬가지로 배열 nums에서 0을 배열을 앞쪽으로 모으기 위해 for 반복문을 작성한다.

  for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < nums.length - 1; j++)
        if (nums[j] == 2) {
            int tmp = nums[j];
            nums[j] = nums[j + 1];
            nums[j + 1] = tmp;
    }