[Extentions] more clear explanation than previous posts!


  • 7

    First, Let us to solve a simpler problem, for input like this

       Input array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0] 
    

    We want the put all the '0' to the left while the '1' to the right.

       Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1] 
    

    How can you do this in only one pass ?

    Here is a possible implementation:

    void segregate0and1(vector<int> arr)
    {
        int size=arr.size();
        /* Initialize left and right indexes */
        int left = 0, right = size-1;
     
        while (left < right)
        {
            /* Increment left index while we see 0 at left */
            while (arr[left] == 0 && left < right)
                left++;
     
            /* Decrement right index while we see 1 at right */
            while (arr[right] == 1 && left < right)
                right--;
     
            /* If left is smaller than right then there is a 1 at left
              and a 0 at right.  Exchange arr[left] and arr[right]*/
            if (left < right)
            {
                  swap(arr[left++], arr[right--]);
            }
        }
    }
    

    Now let us solve the 3 color problem, it is just a easy extension based on the above problem.

    The most important thing is to make sure you know that to solve the above problem, we use 2 pointers.

    Now this problem need 3 pointers.

              L0      array[0...L0-1]  all are 0
              L1      array[L0...L1-1]  all are 1
              unknown    array[L1...L2] 
              L2      array[L2+1...N]  all are 2
    

    Based on the above definition, it is much more easy to understand the algorithm like this.

           L0 := 0; L1:= 0; L2 := N-1;
           while L1 <= L2 do
           Invariant: a[0..L0-1]=0 and a[L0..L1-1]=1 and a[L2+1..N]=2; a[L1..L2] are unknown.
           case a[L1] in
               0: swap a[L0] and a[L1]; L0++; L1++
               1: L1++
               2: swap a[L1] and a[L2];  L2--
    

    The above index explanation can be viewed in this images.

    L1 means mid and L2 means Hi

    enter image description here

    Based on the above explanation, we get the final AC implementation like this

    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            int len=nums.size();
            if(len<=1)  return;
            int one=0, two=len-1, zero=0;
            while(one<=two){
                if(nums[one]==0)  swap(nums[one++], nums[zero++]);
                else if (nums[one]==2)  swap(nums[one], nums[two--]);
                else  one++;
            }
        }
    };
    

    Thanks the posts from G4G

    http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/

    UPDATE @ 2016/03/04

    How to solve the problem if there are K colors ?

    Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.

    We can use the previous position to store the count of all the K value, use the position K-1 to store the
    occurrence of the number K.

    To distinguish from the recorded number, we use negative number to store the occurrence.

    class Solution{
    public:
        /**
         * @param colors: A list of integer
         * @param k: An integer
         * @return: nothing
         */
        void sortColors2(vector<int> &colors, int k) {
            for (int i = 0; i < colors.size(); ++i) {
                if (colors[i] > 0) {
                    int pos = colors[i] - 1;
                    if (colors[pos] <= 0) {  // Bucket exists.
                        --colors[pos];
                        colors[i] = 0;
                    }
                    else {  // Init a new bucket.
                        colors[i] = colors[pos];
                        colors[pos] = -1;
                        --i;
                    }
                }
            }
    
            for (int i = colors.size() - 1, pos = k - 1; pos >= 0; --pos) {
                while (colors[pos] < 0) {  // Reorder the color by count of each bucket.
                    ++colors[pos];
                    colors[i--] = pos + 1;
                }
            }
        }
    };
    

  • 1

    Thanks to the post from @StefanPochmann

    The wiggle sort problem is just based on this problem.

    Here is the solution

    class Solution {
    public:
        void wiggleSort(vector<int>& nums) {
            int n=nums.size();
            auto midptr=nums.begin()+n/2;
            nth_element(nums.begin(), midptr, nums.end());
            int mid=*midptr;
            
            #define A(i) nums[(2*(i)+1)%(n|1)]
            
            int i=0, j=0, k=n-1;
            while(j<=k){
                if(A(j)>mid)
                    swap(A(i++), A(j++));
                else if(A(j)<mid)
                    swap(A(j), A(k--));
                else 
                    j++;
            }
        }
    };

  • 0
    This post is deleted!

  • 0

    I have edit to add the reference to you. I am really sorry.


  • 0

    Alright, thanks.


  • 0
    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            int n=nums.size();
            int pos0=0, pos1=0, pos2=n-1;
            while(pos1<=pos2){
                if(nums[pos1]==0)  swap(nums[pos0++], nums[pos1++]);
                else if(nums[pos1]==2)  swap(nums[pos1], nums[pos2--]);
                else    pos1++;
            }
        }
    };

  • 0

    I mistake the pos1<pos2 , can not AC !


  • 0
    2

    I made the below error ......

    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            int zero = 0, one = 0, two = nums.size()-1;
            for(int i = 0; i <= two; i++) {
                if(nums[i] == 0) {
                    swap(nums[zero++], nums[i]);
                    one++;
                }
                else if(nums[i] == 2) {
                    swap(nums[two--], nums[i]);
                }
                else{
                    one++;
                }
            }
        }
    };

  • 0
    X
    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            if (nums.size() == 0 || nums.size() == 1) return;
            int lowPartition = 0, highPartition = nums.size() - 1;
            int i = 0;
            while (i <= highPartition) {
                if (is_low(nums[i])) {
                    swap(nums[lowPartition], nums[i]);
                    lowPartition++;
                    i++;
                } else if (is_high(nums[i])) {
                    swap(nums[highPartition], nums[i]);
                    highPartition--;
                } else {
                    i++;
                }
            }
        }
    };

  • 0
    N

    Generic Solution does not work for many test cases for instance try for [2,2] and k=3


  • 0
    F

    @neer1304 The input is ensured to include all the number from 1 to k


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.