[Swift]LeetCode75. 颜色分类 | Sort Colors - Swift 教程-OStack程序员社区-中国程序员成长平台

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

[Swift]LeetCode75. 颜色分类 | Sort Colors

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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]

Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

8ms

 1 class Solution {
 2     func sortColors(_ nums: inout [Int]) {
 3         
 4         var i = 0
 5         var left = 0
 6         var right = nums.count - 1
 7         
 8         while i <= right {
 9             if nums[i] == 0 {
10                 nums.swapAt(i, left)
11                 i += 1
12                 left += 1
13             } else if nums[i] == 1 {
14                 i += 1
15             } else {
16                 nums.swapAt(i, right)
17                 right -= 1
18             }
19         }
20     }
21 }

12ms

 1 class Solution {
 2     /// 桶排序法, 0...red 都是 0，blue...nums.count-1 都是2
 3     func sortColors(_ nums: inout [Int]) {
 4         var red = -1
 5         var blue = nums.count
 6         var i = 0
 7         
 8         while i < blue {
 9             if nums[i] == 0 {
10                 red += 1
11                 (nums[i], nums[red]) = (nums[red], nums[i])
12                 i += 1
13             } else if nums[i] == 2 {
14                 blue -= 1
15                 (nums[i], nums[blue]) = (nums[blue], nums[i])
16             } else {
17                 i += 1
18             }
19         }
20     }
21 }

16ms

 1 class Solution {
 2     func sortColors(_ nums: inout [Int]) {
 3         var zeroCounter = 0
 4         var oneCounter = 0
 5         var twoCounter = 0
 6         
 7         for each in nums{
 8             if each == 0{
 9                 zeroCounter += 1
10             }else if each == 1{
11                 oneCounter += 1
12             }else if each == 2{
13                 twoCounter += 1
14             }
15         }
16         
17         for each in 0..<zeroCounter{
18             nums[each] = 0
19         }
20         
21         for each in 0..<oneCounter{
22             nums[zeroCounter+each] = 1
23         }
24         
25         for each in 0..<twoCounter{
26             nums[zeroCounter+oneCounter+each] = 2
27         }
28         
29     }
30 }

20ms

 1 class Solution {
 2     func sortColors(_ nums: inout [Int]) {
 3             var redCount = 0, whiteCount = 0, blueCount = 0
 4     for i in 0..<nums.count {
 5         if nums[i] == 0 {
 6             redCount = redCount + 1
 7             nums[redCount - 1] = 0
 8         } else if nums[i] == 1 {
 9             whiteCount = whiteCount + 1
10         } else {
11             blueCount = blueCount + 1
12         }
13     }
14     for i in redCount..<redCount+whiteCount {
15         nums[i] = 1
16     }
17     for i in redCount+whiteCount..<nums.count {
18         nums[i] = 2
19     }
20     }
21 }