leetcode Sort Colors

leetcode Sort Colors

Given an array with n objects colored red, white or blue, sort them 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.

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 an one-pass algorithm using only constant space?

题目地址:leetcode Sort Colors

题目大意: 一个数组中,0代表红色,1代表白色,2代表蓝色。请按照红-白-蓝色的顺序排好。不能使用sort函数。

 

思路:

方法1

就三种元素,直接计数排序即可。

C++

Python

 

方法2

交换元素,设l为0结尾+1,r为2的开头-1的位置

于是我们可以用i 遍历, 从[0,r]

  • nums[i] == 0:   交换nums[l] 和nums[i],l++,i++
  • nums[i] == 2: 交换nums[r]和nums[i],r–(注意交换后nums[i]可能变为0,因此i不+1)
  • nums[i] == 1: i++

C++

Python

 

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Sort Colors
本文地址:https://www.hrwhisper.me/leetcode-sort-colors/

听说长得好看的已经打赏了

Leetcode . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *