[LeetCode] 75. Sort Colors 颜色排序

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 75. Sort Colors 颜色排序,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given an array 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.html

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

Note: You are not suppose to use the library's sort function for this problem.python

Example:数组

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:post

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 a one-pass algorithm using only constant space?this

对3种颜色进行排序,用0,1,2三个数字表明不一样颜色。题目要求不能使用sort function。url

的解法1:counting sort计数统计,two pass。先用HashMap或Array统计每一个数字的个数,而后分别迭代0,1,2的个数,over write到数组。spa

解法2:双指针two pointers,one pass。若是算上迭代用的index,就有三个指针。利用只有3个颜色的特色,使用left, right双指针来指向记录处理过的0和2的边界位置。一开始,两个指针分别指向头和尾,而后遍历数组。当遇到0时,和left指针的数交换,而后将left指针向右移1位。当遇到2时,和右指针的数交换,而后将右指针向左移1位。遇到1时,不作处理,进入到下一数。当遇到right指针时,就已经排完序了,全部0都被交换到了前面,全部2都被交换到了后面。指针

Java: one passhtm

public class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int i = 0;
        while(i <= right){
            if(nums[i] == 0){
                swap(nums, i, left);
                left++;
                i++; // 由于左边的已经检查过,因此能够进入下一个
            } else if(nums[i] == 2){
                swap(nums, i, right);
                right--; // 由于交换过来的数还没检查过,因此不能i++
            } else {
                i++;
            }
        }
    }
    
    private void swap(int[] nums, int i1, int i2){
        int tmp = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = tmp;
    }
}

Python: one pass

class Solution(object):
    def sortColors(self, nums):
        def triPartition(nums, target):
            left, idx, right = 0, 0, len(nums) - 1
            
            while idx <= right:
                if nums[idx] < target:
                    nums[left], nums[idx] = nums[idx], nums[left]
                    left += 1
                    idx += 1
                elif nums[idx] > target:
                    nums[idx], nums[right] = nums[right], nums[idx]
                    right -= 1
                else:
                    idx += 1
                    
        triPartition(nums, 1)

Python:

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i, j, k = 0, 0, len(nums) - 1
        while j <= k:  # while j < len(nums): or while j < k:  
            if nums[j] == 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j += 1  # important
            elif nums[j] == 2:
                nums[j], nums[k] = nums[k], nums[j]
                k -= 1
            else:
                j += 1  

Python: one pass, no swap

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = j = 0
        for k in xrange(len(nums)):
            v = nums[k]
                nums[k] = 2
            if v < 2:
                nums[j] = 1
                j += 1
            if v == 0:
                nums[i] = 0
                i += 1    

C++: two pass, Time: O(n), Space: O(1)

class Solution {
public:
    void sortColors(int A[], int n) {
        int count[3] = {0}, idx = 0;
        for (int i = 0; i < n; ++i) ++count[A[i]];
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < count[i]; ++j) {
                A[idx++] = i;
            }
        }
    }
};

C++: one pass, Time: O(n), Space: O(1)

class Solution {
public:
    void sortColors(int A[], int n) {
        int red = 0, blue = n - 1;
        for (int i = 0; i <= blue; ++i) {
            if (A[i] == 0) {
                swap(A[i], A[red++]);
            } else if (A[i] == 2) {
                swap(A[i--], A[blue--]);
            }
        }
    }
};

C++:

    class Solution {
    public:
        void sortColors(int A[], int n) {
            int second=n-1, zero=0;
            for (int i=0; i<=second; i++) {
                while (A[i]==2 && i<second) swap(A[i], A[second--]);
                while (A[i]==0 && i>zero) swap(A[i], A[zero++]);
            }
        }
    };

  

  

相似题目:

[LeetCode] 15. 3Sum 三数之和

  

All LeetCode Questions List 题目汇总