前言

脑筋急转弯型更注重逻辑，不太考察具体的数据结构，可以有效的训练思维。通过颜色分类，完成堆排、单、双指针的练习。同时，注重代码的简洁性、程序性(非简单逻辑如很多判断)。最后，对显示隐式的重复逻辑要做到简化。

一、颜色分类

二、逻辑训练（纯逻辑所以用两种语言）

1、Java

package com.xhu.offer.top100;

//颜色分类
public class SortColors {
    
    /* target：对数组进行排序。 M1-手写堆排 */
    public void sortColors(int[] nums) {
    
        //1-建堆，从最后一棵子树到根树进行调整，即从最后一个叶子节点的父节点到root节点进行调整。
        int n = nums.length;
        for (int i = (n - 1) / 2; i >= 0; --i) adjustHeap(nums, i, n);
        //2-堆排
        for (int i = 1; i < n; i++) {
    
            int t = nums[n - i];
            nums[n - i] = nums[0];
            nums[0] = t;

            adjustHeap(nums, 0, n - i);
        }
        return;
    }

    /** * 堆排关键操作，给定位置，以O(logN)来进行调整堆 * * @param nums * @param k */
    private void adjustHeap(int[] nums, int k, int n) {
    
        int val = nums[k];
        for (int i = 2 * k + 1; i < n; i = i * 2 + 1) {
    
            //确定左右子树谁更大
            //bug1:i+1也不能超过n
            if (i + 1 < n && nums[i] < nums[i + 1]) i++;
            //判断是否需要调整
            if (nums[i] < val) break;
            //需要调整
            nums[k] = nums[i];
            //继续向下影响
            k = i;
        }
        nums[k] = val;
    }
}

//题目要求：你能想出一个仅使用常数空间的一趟扫描算法吗？
class SortColors2 {
    
    /* target：一趟扫描，空间O(1)，纯纯的老筋急转弯型题，逻辑训练。 题目特点，只有0，1，2三个元素， */
    public void sortColors(int[] nums) {
    

    }

    /* 非一趟扫描，记录0，1，2分别有多少个，然后在来一趟覆盖。 */
    public void sortColors2(int[] nums) {
    
        int[] colors = new int[3];
        for (int num : nums) ++colors[num];

        int cnt = 0, val = 0;
        for (int color : colors) {
    
            for (int i = 0; i < color; i++) {
    
                nums[cnt++] = val;
            }
            ++val;
        }
    }

    /* 除了重写，根据题目只有三种值的特点，可以遍历两次，第一次把0交换到前面去，第二次把1交换到0的后面，2就自然在后面了。 */
    public void sortColors3(int[] nums) {
    
        int cnt = 0, n = nums.length;

        int p = 0;//指向需要交换0的位置。
        //把0放在最前面
        while (cnt < n) {
    
            //交换位置
            if (nums[cnt] == 0) {
    
                swap(nums, cnt, p);
                //更新指针p的位置为下一个
                ++p;
            }
            //往后遍历
            ++cnt;
        }
        //把1放到0的后面
        cnt = p;
        while (cnt < n) {
    
            //交换位置
            if (nums[cnt] == 1) {
    
                swap(nums, cnt, p);
                //更新指针p指向下一个需要更新的位置。
                ++p;
            }
            //往后遍历，更新cnt
            ++cnt;
        }
    }

    /** * 将数组中位置i和位置j的元素交换 * * @param nums * @param i * @param j */
    private void swap(int[] nums, int i, int j) {
    
        int val = nums[i];
        nums[i] = nums[j];
        nums[j] = val;
    }

    /* 单指针-defect：需要两趟扫描，其实把0放在头部，把2放在尾部，那么1就固定在中间了。 M-双指针，一个指针在头部，固定0；另一个指针在尾部，固定2.根据夹逼准则，1就自然固定在中间了。 */
    public void sortColors4(int[] nums) {
    
        int bn = 0, ed = nums.length - 1;

        int cnt = 0, n = ed;
        while (cnt <= ed) {
    
            //固定0
            if (0 == nums[cnt]) {
    
                swap(nums, cnt, bn);
                //更新前指针，为下一次交换0做准备。
                ++bn;
            }
            //固定2
            if (2 == nums[cnt]) {
    
                swap(nums, cnt, ed);
                //更新后指针，为下一次交换2做准备。
                --ed;
                //bug1:如果和2交换回来的是0，那么还得交换一次。
                //bug2:如果和2交换回来的是2，那么也得交换一次。
                if (nums[cnt] == 0 || 2 == nums[cnt]) continue;
            }
            //往后继续遍历

            ++cnt;
        }
    }

    /* M-双指针-defect：很多交换是没有必要的，为了不写太多判断，所以让CPU直接算就可以了。CPU喜欢计算，不喜欢判断！ 而且，显示和隐式的相似逻辑，就没必要重复写了。 1-显示重复逻辑：如数组的两值交换；两个一样的循环结构--数组遍历； 2-隐式重复逻辑：当遇到2与2交换时，我们可以从尾节点开始判断该值是否为2，然后--即可；换会1，就和前指针交换。 但是没必要这样，换会2，再进入循环，再换一次即可，该逻辑已经写好了；同理换回1，再进入循环经过循环体，交换以下即可，该逻辑也写好了。 注：写代码没必要完整按照人想的步骤进行，也需考虑代码简洁，CPU执行效率。以这两点为基础，换一个编程逻辑替换以前的简单逻辑。 但是，不需要遍历到数组末尾，只需要遍历到尾指针即可！这种没必要的逻辑可以省略。 M-双指针-省略不必要的逻辑-遍历到尾指针即可。 */
    public void sortColors5(int[] nums) {
    
        int bn = 0, ed = nums.length - 1;

        int cnt = 0;
        while (cnt <= ed) {
    
            //固定0
            if (0 == nums[cnt]) {
    
                swap(nums, cnt, bn);
                //更新前指针，为下一次交换0做准备。
                ++bn;
            }
            //固定2
            if (2 == nums[cnt]) {
    
                swap(nums, cnt, ed);
                //更新后指针，为下一次交换2做准备。
                --ed;
                //bug1:如果和2交换回来的是0，那么还得交换一次。
                //bug2:如果和2交换回来的是2，那么也得交换一次。
                if (nums[cnt] == 0 || 2 == nums[cnt]) continue;
            }
            //往后继续遍历
            ++cnt;
        }
    }
}

2、Go

func sortColors(nums []int)  {
    
    n := len(nums);
    //调整堆
    for i := (n - 1) / 2;i >= 0;i--{
    
        adjustHeap(nums,i,n);
    }
    //堆排
    for i:=1;i<n;i++{
    
        t:=nums[n-i];
        nums[n-i] = nums[0];
        nums[0] = t;

        adjustHeap(nums,0,n-i);
    }

}
func adjustHeap(nums []int,k int,n int){
    
    val := nums[k];
    for i:= 2 * k + 1;i < n;i = i * 2 + 1{
    
        //确定nums[i+1]是否大于nums[i]
        if i + 1 < n && nums[i + 1] > nums[i] {
    
            i++;
        }
        //确定是否需要调整
        if nums[i] < val {
    
            break;
        }
        //确定调整
        nums[k] = nums[i]
        k = i;
    }
    nums[k] = val;
}

func sortColors(nums []int)  {
    
    colors := [3]int{
    };

    for _,val := range nums {
    
        colors[val]++;
    }
    cnt,val := 0,0;
    for _,n := range colors{
    
        for i := 0;i < n;i++{
    
            nums[cnt] = val;
            cnt++;
        }
        val++;
    }

}

总结

1）堆排–key–adjustHeap(int[],int,int)
2）利用问题的特性。
3）显示隐式重复逻辑的避免与改进。

参考文献

[1] LeetCode 颜色分类