Sorting: 75. Sort Colors

75. Sort Colors

 

 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # We will use the integers 0, 1, and 2
        rgb = [0, 0, 0] 

        for n in nums:
            rgb[n] += 1

        i = 0
        for n in range(len(rgb)):
            for _ in range(rgb[n]):
                nums[i] = n
                i += 1

https://youtu.be/4xbWSRZHqac?si=eIOF8amP3_ulRLQu

 

 

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l, r = 0, len(nums)-1
        i = 0

        def swap(i, j):
            tmp = nums[i]
            nums[i] = nums[j]
            nums[j] = tmp

        while i<=r:
            if nums[i] == 0:
                swap(l, i)
                l+=1
            elif nums[i] == 2:
                swap(r, i)
                r -= 1
                i -= 1
            i += 1

 

추가 문제

280. Wiggle Sort: https://leetcode.com/problems/wiggle-sort/description/

324. Wiggle Sort II: https://leetcode.com/problems/wiggle-sort-ii/description/

 

최종 코드

버켓 정렬 : Burket Sort  ==> Count 후, 다시 정렬

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        Count = [0] * 3
        for n in nums:
            Count[n]+=1

        idx=0
        for c in range(len(Count)):
            for i in range(Count[c]):
                nums[idx] = c
                idx +=1