• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[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?

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

此题中,我们使用整数 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap