LeetCode 75. Sort Colors [Swift 题解]

题目

Given an array 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.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]  
Output: [0,0,1,1,2,2]  

思路

思路一: 非in place解法,直接用一个dictionary记住0,1,2的个数,然后把它们依次放到array里面.

func sortColors(_ nums: inout [Int]) {  
        var dict = [0:0, 1:0, 2:0]

        for num in nums {
            let current = dict[num]!
            dict[num] = (current + 1)
        }

        var result = [Int]()
        for key in 0...2 {
            let current = Array(repeating: key, count: dict[key]!)
            result.append(contentsOf: current)
        }

        nums = result
    }

思路二: in place解法,需要定义两个boundary, End of 0, Start of 2, 然后iterate整个数组依次update, 参考YouTube

func sortColors(_ nums: inout [Int]) {  
        var i = 0
        var k = nums.count - 1

        var j = 0

        while j <= k {
            switch nums[j] {
            case 0:
                nums.swapAt(i, j)
                i += 1
                j += 1
            case 1:
                j += 1
            case 2:
                nums.swapAt(j, k)
                k -= 1
            default: break
            }
        }
    }

chenbo

编程爱好者

Singapore