75. Sort Colors

LeetCode Link (opens in a new tab)

Sorting

Description

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 cases

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.

Approach

주어진 배열을 빌트인 정렬 함수를 사용하지 않고, in-place로 정렬하는 문제이다

Solution Code

var sortColors = function(nums) {
  let min
  let len = nums.length
  for (let i = 0; i < len - 1; i += 1) {
    min = i
    for (let j = i + 1; j < len; j += 1) {
      if (nums[j] < nums[min]) {
        min = j
      }
    }
 
    if (min !== i) {
      let tmp = nums[min]
      nums[min] = nums[i]
      nums[i] = tmp
    }
  }
};

Complexity

• time complexity : $O(n)$
• space complexity : $O(1)$