【Leetcode】75. Sort Colors

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

1 可以使用counting sort,先遍历一遍array,找出0,1,2的个数,然后再去overwrite array,所以是一个two pass的过程

2 使用partition方法,采用三个指针,red,white,blue,red=white=0,blue=n-1,循环条件是white<=blue,当nums[white]=2时,和nums[n-1]交换,同时blue-1,这里是为了将blue的都放在最后面去;当nums[white]=1的时候,不需要交换任何的,直接把white指针加1就行;当nums[white]=0的时候,和nums[red]进行交换,同时把white和red的指针都加1



最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容