🌕 🌗 75. 颜色分类

难度: 🌕 🌗

问题描述

---

解法 1 - 2 遍遍历

class Solution {
    public void sortColors(int[] nums) {
        // 思路：
        // 2 遍扫描，第一次 将 0 移到所有的 1 & 2 前面
        // 第二次 将 1 移到 2 的前面
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while(left < right) {
            while(left < right && nums[left] == 0) {
                left ++;
            }
            while(left < right && nums[right] > 0) {
                right --;
            }
            swap(nums, left, right);
            left ++;
            right --;
        }
        left = 0;
        right = len - 1;
        while(left < right) {
            if(nums[left] == 0) {
                left ++;
            } else {
                break;
            }
        }
        // [left] != 0
        while(left < right) {
            while(left < right && nums[left] == 1) {
                left ++;
            }
            while(left < right && nums[right] == 2) {
                right --;
            }
            swap(nums, left, right);
            left ++;
            right --;
        }
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

---

输出 1

---

解法 2 - 三指针

class Solution {
    public void sortColors(int[] nums) {
        // 思路：
        // 一遍遍历 - 3 个指针
        // 一个指针 zero 记录 0 截止
        // 一个指针 left 记录 当前 
        // 一个指针 right 记录 右边界 
        // 当遇到 [0, 1] 时，与 zero & left 有关
        // 当遇到 [0, 2] 时，与 zero & right 有关
        // 当遇到 [1, 2] 时，与 left & right 有关
        int len = nums.length;
        int zero = -1;
        int left = 0;
        int right = len - 1;
        while(left <= right) {
            if(nums[left] > nums[right]) {
                swap(nums, left, right);
            }
            // [left] <= [right]
            if(nums[left] == 0) {
                // 判断 zero 后面是否还有 1 可以与 [left] 交换
                if(zero < left - 1) {
                    swap(nums, zero + 1, left);
                }
                zero ++;
                left ++;
            } else if(nums[left] == 1) {
                left ++;
            }else if (nums[left] == 2) {
                right --;
            }
        }
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }    
}

---

输出 2