LeetCode题解75.sort-colors

题目地址

https://leetcode.com/problems/sort-colors/description/

题目描述

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.

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.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
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 a one-pass algorithm using only constant space?

思路

这个问题是典型的荷兰国旗问题 （https://en.wikipedia.org/wiki/Dutch_national_flag_problem）。 因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。

有两种解决思路。

解法一

• 遍历数组，统计红白蓝三色球（0，1，2）的个数
• 根据红白蓝三色球（0，1，2）的个数重排数组

这种思路的时间复杂度：$O(n)$，需要遍历数组两次。

解法二

我们可以把数组分成三部分，前部（全部是0），中部（全部是1）和后部（全部是2）三个部分。每一个元素（红白蓝分别对应0、1、2）必属于其中之一。将前部和后部各排在数组的前边和后边，中部自然就排好了。

我们用三个指针，设置两个指针begin指向前部的末尾的下一个元素（刚开始默认前部无0，所以指向第一个位置），end指向后部开头的前一个位置（刚开始默认后部无2，所以指向最后一个位置），然后设置一个遍历指针current，从头开始进行遍历。

这种思路的时间复杂度也是$O(n)$, 只需要遍历数组一次。

关键点解析

• 荷兰国旗问题
• counting sort

代码

代码支持： Python3

Python3 Code:

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        p0 = cur = 0
        p2 = len(nums) - 1
        
        while cur <= p2:
            if nums[cur] == 0:
                nums[cur], nums[p0] = nums[p0], nums[cur]
                p0 += 1
                cur += 1
            elif nums[cur] == 2:
                nums[cur], nums[p2] = nums[p2], nums[cur]
                p2 -= 1
            else:
                cur += 1

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解深度优先遍历和回溯的关系？

深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。

LeetCode题解盲人买袜子。

他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈

LeetCode题解白石搭白塔

输入黑块和白块的数量，用输入的方块数目建塔，输出最大高度和种数，两种方法至少一层颜色不同才能算不同的方法塔满足下列要求:1. 塔底层块数和高度数值相同，逐层递减1，最高层为12. 每层颜色相同

LeetCode题解分鸡块

外卖鸡块分别有 4，6，12 块， 每 固定块数不能分开装， 用户给一个数字， 要求返回满足用户订单（可以等于也可以大于）的最少的盒数的组合