Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/75.html

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

 

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

 

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2.

 

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Algorithm

Freq stats

The essence of this question is still a sorting question. The question gives a hint that it can be sorted by counting. You need to traverse the array twice. Then let’s look at this method first. Because there are only three different elements in the array, it is very easy to implement. easy.

  1. First traverse the original array and record the numbers of 0, 1, and 2 respectively.
  2. Then update the original array and assign 0, 1, 2 according to the number.

Two pointers

In the problem, it is necessary to traverse the array only once to solve it, so you need to use a double pointer to do it, and move from the beginning and the end of the original array to the center.

  1. Define the red pointer to point to the beginning and the blue pointer to point to the end.
  2. Traverse the original array from the beginning,
    • if it encounters 0, exchange the value and the value pointed to by the red pointer, and move the red pointer one bit backward.
    • If it encounters 2, exchange the value and the value pointed to by the blue pointer, and move the blue pointer forward one bit. If it encounters 1, continue to traverse.

Code

  • import java.util.Arrays;
    
    public class Sort_Colors {
    
    	public static void main(String[] args) {
    		Sort_Colors out = new Sort_Colors();
    		Solution s = out.new Solution();
    
    		s.sortColors(new int[]{0, 0});
    	}
    
    	public class Solution {
    	    public void sortColors(int[] nums) {
    	        if (nums == null || nums.length == 0) {
    	            return;
    	        }
    
    	        // idea is: move all "2" to end, all "0" front, then 1 is done itself
    	        // 3 pointers, last-0, current scan, first-2
    
    	        int p0 = 0; // last-0
    	        int p2 = nums.length - 1;
    	        int p = 0; // scan pointer
    
    	        while (p <= p2) {
    
    	            if (nums[p] == 0) {
    
    	                // swap 0 to front. eg: 0,1,1,1,1,1,1,0.      or: 0,0,0,0,0,1
    
    	                int tmp = nums[p0];
    	                nums[p0] = nums[p];
    	                nums[p] = tmp;
    
    	                p0++;
    	                p++;
    
    	            } else if (nums[p] == 2) {
    	                // swap "2" to end
    	                int tmp = nums[p2];
    	                nums[p2] = nums[p];
    	                nums[p] = tmp;
    
    	                p2--;
    	            } else { // assumption: only 0,1,2, so here nums[p]==1
    	                p++;
    	            }
    	        }
    	    }
    	}
    
    	public void sortColors(int[] A) {
    	    if(A==null || A.length==0)
    	        return;
    	    int idx0 = 0;
    	    int idx1 = 0;
    	    for(int i=0;i<A.length;i++)
    	    {
    	        if(A[i]==0)
    	        {
    	            A[i] = 2;
    	            A[idx1++] = 1;
    	            A[idx0++] = 0;
    	        }
    	        else if(A[i]==1)
    	        {
    	            A[i] = 2;
    	            A[idx1++] = 1;
    	        }
    	    }
    	}
    
    }
    
    ############
    
    class Solution {
        public void sortColors(int[] nums) {
            int i = -1, j = nums.length;
            int cur = 0;
            while (cur < j) {
                if (nums[cur] == 0) {
                    swap(nums, cur++, ++i);
                } else if (nums[cur] == 1) {
                    ++cur;
                } else {
                    swap(nums, cur, --j);
                }
            }
        }
    
        private void swap(int[] nums, int i, int j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    
  • // OJ: https://leetcode.com/problems/sort-colors/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        void sortColors(vector<int>& nums) {
            vector<int> cnt(3, 0);
            for (int n : nums) cnt[n]++;
            int i = 0;
            for (int j = 0; j < 3; ++j) {
                while (cnt[j]--) nums[i++] = j;
            }
        }
    };
    
  • class Solution:
        def sortColors(self, nums: List[int]) -> None:
            """
            Do not return anything, modify nums in-place instead.
            """
            i, j = -1, len(nums)
            cur = 0
            while cur < j:
                if nums[cur] == 0:
                    i += 1
                    nums[cur], nums[i] = nums[i], nums[cur]
                    cur += 1
                elif nums[cur] == 1:
                    cur += 1
                else:
                    j -= 1
                    nums[cur], nums[j] = nums[j], nums[cur]
    
    ############
    
    class Solution(object):
      def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        x = y = z = -1
        for i in range(0, len(nums)):
          if nums[i] == 0:
            x += 1
            y += 1
            z += 1
            if z != -1:
              nums[z] = 2
            if y != -1:
              nums[y] = 1
            nums[x] = 0
          elif nums[i] == 1:
            y += 1
            z += 1
            nums[z] = 2
            if x != -1:
              nums[x] = 0
            if y != -1:
              nums[y] = 1
          elif nums[i] == 2:
            z += 1
            if y != -1:
              nums[y] = 1
            if x != -1:
              nums[x] = 0
            nums[z] = 2
    
    
  • func sortColors(nums []int) {
    	i, j, cur := -1, len(nums), 0
    	for cur < j {
    		if nums[cur] == 0 {
    			i++
    			nums[cur], nums[i] = nums[i], nums[cur]
    			cur++
    		} else if nums[cur] == 1 {
    			cur++
    		} else {
    			j--
    			nums[cur], nums[j] = nums[j], nums[cur]
    		}
    	}
    }
    
  • /**
     Do not return anything, modify nums in-place instead.
     */
    function sortColors(nums: number[]): void {
        let n = nums.length;
        if (n < 2) return;
        let p0 = 0,
            p2 = n - 1;
        let p1 = 0;
        while (p1 <= p2) {
            if (nums[p1] == 0) {
                [nums[p0], nums[p1]] = [nums[p1], nums[p0]];
                p0++;
                p1++;
            } else if (nums[p1] == 1) {
                p1++;
            } else {
                [nums[p1], nums[p2]] = [nums[p2], nums[p1]];
                p2--;
            }
        }
    }
    
    
  • impl Solution {
        pub fn sort_colors(nums: &mut Vec<i32>) {
            let mut l = 0;
            let mut r = nums.len() - 1;
            let mut i = 0;
            while i <= r {
                match nums[i] {
                    2 => {
                        nums.swap(i, r);
                        match r {
                            0 => return,
                            _ => r -= 1,
                        }
                    }
                    n => {
                        if n == 0 {
                            nums.swap(i, l);
                            l += 1;
                        }
                        i += 1;
                    }
                }
            }
        }
    }
    
    
  • public class Solution {
        public void SortColors(int[] nums) {
            int i = -1, j = nums.Length, k = 0;
            while (k < j) {
                if (nums[k] == 0) {
                    swap(nums, ++i, k++);
                } else if (nums[k] == 2) {
                    swap(nums, --j, k);
                } else {
                    ++k;
                }
            }
        }
    
        private void swap(int[] nums, int i, int j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    

All Problems

All Solutions