Sort Colors
这题说实话，最直观的想法没有想到emmmm，先构造一个hash然后在进行重新构造的思想，我觉得挺好的。不过它要求做one-pass，就重新想了一个。这题的主要考点：
- one-pass和two-pass的区别
- test_case的考虑
因为只能扫描数组一遍，所以自然想到肯定是交换，然后又因为这题只有0，1，2三个数，所以只要设置两个指针，碰到0往左交换，碰到2往右交换，就可以了。
只是要注意的一点是，碰到2的时候往右交换，你不知道是不是交换到0，所以遍历的下标不能移动。碰到0的时候往左交换，肯定是没事的，因为左边不可能还有2（如有2肯定就交换过了）
代码
class Solution:def sortColors(self, nums):""":type nums: List[int]:rtype: void Do not return anything, modify nums in-place instead."""l, m, h = 0, 0, len(nums)-1while(m<=h):if nums[m] == 1:m+=1elif nums[m] == 0:nums[l], nums[m] = nums[m], nums[l]l+=1m+=1elif nums[m] == 2:nums[m], nums[h] = nums[h], nums[m]h-=1
leetcode上最快的代码
我感觉它扫了两遍，其实更慢。不过它提供了一种很好的思路。以后不管0-n,其实都能这样做。
先扫一遍，把最小的放一边，然后从新位置开始再扫一遍，把第二小的放一边
class Solution:def sortColors(self, nums):""":type nums: List[int]:rtype: void Do not return anything, modify nums in-place instead."""zero = 0for i in range(len(nums)):if nums[i] == 0:nums[i], nums[zero] = nums[zero], nums[i]zero += 1one = zerofor i in range(one, len(nums)):if nums[i] == 1:nums[i], nums[one] = nums[one], nums[i]one += 1