首页 > 代码库 > LeetCode 75. Sort Colors(排序颜色)
LeetCode 75. 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.
click to show follow up.
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?
题目标签:Array
Java Solution:
Runtime beats 55.91%
完成日期:07/24/2017
关键词:Array
关键点:用two pointers,一头一尾放置红色和蓝色,保留白色在中间
1 public class Solution 2 { 3 public void sortColors(int[] nums) 4 { 5 int red = 0; 6 int blue = nums.length-1; 7 8 for(int i=0; i<=blue; i++) 9 { 10 if(nums[i] == 0) // if find 0, swap with red pointer 11 { 12 int temp = nums[i]; 13 nums[i] = nums[red]; 14 nums[red] = temp; 15 16 red++; 17 } 18 else if(nums[i] == 2) // if find 2, swap with blue pointer 19 { 20 int temp = nums[i]; 21 nums[i] = nums[blue]; 22 nums[blue] = temp; 23 24 i--; 25 blue--; 26 } 27 28 } 29 } 30 }
参考资料:
http://www.cnblogs.com/grandyang/p/4341243.html
LeetCode 算法题目列表 - LeetCode Algorithms Questions List
LeetCode 75. Sort Colors(排序颜色)