LeetCode: Sort Colors

 

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.

 

이번 문제는 단순히 0, 1, 2의 순서만 맞추면 되는 문제이다. 

 

근데 나는 재미로 merge sort, heap sort, 단순 구현으로 모두 구현해봤다. 

 

문제푸는 코드는 아래에 소개했다.

 

---

merge sort로 맞추기

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        if len(nums) <= 1:
            return nums

        mid = len(nums)//2
        left = self.sortColors(nums[:mid])
        right = self.sortColors(nums[mid:])
        
        l, r = 0, 0
        res = []

        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                res.append(left[l])
                l += 1
            else: 
                res.append(right[r])
                r += 1
        
        while l < len(left):
            res.append(left[l])
            l += 1
        while r < len(right):
            res.append(right[r])
            r += 1

        for i in range(len(nums)):
            nums[i] = res[i]
        return res

 

 

heap sort로 맞추기

 

 

 

class Solution(object):
    def heapify(self, arr_len, arr):
        self.last_parent = arr_len//2 -1
        for current in range(self.last_parent, -1, -1):
            while current <= self.last_parent:
                self.child = current * 2 + 1
                self.sibling = current * 2 + 2
                if self.sibling < arr_len and arr[self.child] < arr[self.sibling]:
                    self.child = self.sibling
                if arr[current] < arr[self.child]:
                    arr[self.child], arr[current] = arr[current], arr[self.child]
                    current = self.child
                else:
                    break 
        return arr

    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        
        for arr_len in range(len(nums), 1, -1):
            nums = self.heapify(arr_len, nums)
            print(nums[0])
            nums[0], nums[arr_len-1] = nums[arr_len-1], nums[0]

        return nums

 

단순 코딩
숫자 짜맞추기

 

 

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        self.zero = 0
        self.one = 0
        self.two = 0
        for num in nums:
            if num == 2:
                self.two += 1
            elif num == 1:
                self.one += 1
            else:
                self.zero += 1
        
        for i in range(self.zero):
            nums[i] = 0
        for j in range(self.zero, self.zero+self.one):
            nums[j] = 1
        for k in range(self.zero+self.one, self.zero+self.one+self.two):
            nums[k] = 2
        # print(self.zero)
        # print(self.one)
        # print(self.two)
        # print(nums)

        return nums