[LeetCode] 75. Sort Colors - 문제풀이

Description

숫자로 색을 나타내는 요소를 가진 배열을 같은색끼리 인접하도록 onepass로 inplace로 정렬 처리하는 문제입니다.

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.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Solution 1. Two pointers

public void sortColors(int[] nums) {
    int len = nums.length;
    int j= 0;
    int k = len-1;

    for (int i = 0; i <= k; i++) {
        if(nums[i] == 0){
            swap(nums,i,j++);
        }else if(nums[i]==2){
            swap(nums,i--,k--);
        }
    }
}

public void swap(int[] nums, int i, int j){
    int temp = nums[j];
    nums[j] = nums[i];
    nums[i] = temp;
}

0의 시작점과 2의 시작점을 가르키는 두개의 포인터를 두고 0과 2가 나올경우 현재요소와 스왑해줍니다. 0으로 스왑한 경우는 해당 위치는 무조건 0이므로 그대로 진행하고 2로 스왑된경우는 스왑된 값을 한 번더 체크하기 위해 i 포인터를 한칸 뒤로 돌린 후 다시 진행합니다.

Reference

Sort Colors - LeetCode