75. Sort Colors

문제링크: https://leetcode.com/problems/sort-colors/description/

인자로 0,1,2만 존재하는 nums 배열을 정렬하는 문제다.

Solution

Table sort with count

0, 1, 2만 존재하기 때문에 각각을 table에 저장한다. 대신 값이 고정이기 때문에 이들의 개수만 저장하고 이후에 nums배열에 적용한다.

Algorithm

• 0, 1, 2의 개수를 저장할 table을 만든다.
• nums를 순회하며 각 숫자의 개수를 센다.
• nums배열을 counter를 통해 순회한다. i숫자의 개수는 j로 nums에 i를 j번 넣고 다음으로 넘어가는 것을 반복해 모두 채워넣는다.

var sortColors = function(nums) {
  // Table sort?
  const table = [0, 0, 0];
  for (let num of nums) {
    table[num]++;
  };
  let counter = 0;
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < table[i]; j++) {
      nums[counter++] = i;
    }
  }
};

O(n) time, O(1) space 복잡도