首页 > 代码库 > 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.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?

我们先用两个指针,一个指向已经排好序的0的序列的后一个点,一个指向已经排好序的2的序列的前一个点。这样在一开始,两个指针是指向头和尾的,因为我们还没有开始排序。然后我们遍历数组,当遇到0时,将其和0序列后面一个数交换,然后将0序列的指针向后移。当遇到2时,将其和2序列前面一个数交换,然后将2序列的指针向前移。遇到1时,不做处理。这样,当我们遍历到2序列开头时,实际上我们已经排好序了,因为所有0都被交换到了前面,所有2都被交换到了后面。

 

public class Solution {    public void sortColors(int[] nums) {        if(nums==null){            return;        }        int len=nums.length;                int left=0;        int right=len-1;        int cur=left;                while(cur<=right){            if(nums[cur]==0){                swap(nums, left, cur);                left++;                cur++;            }            else if(nums[cur]==2){                swap(nums, right, cur);                right--;            }            else{                cur++;            }        }            }        public void swap(int[] nums, int i, int j){        int temp=nums[i];        nums[i]=nums[j];        nums[j]=temp;    }}

 

LeetCode-Sort Colors