【重点】【三指针】【荷兰国旗问题】【快排】75.颜色分类

题目

Python 三指针

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left, cur, right = 0, 0, len(nums)-1
        while cur <= right: # 注意这里需要有"=", cur需要遍历[left, right]内每一个值
            if nums[cur] == 0:
                nums[left], nums[cur] = nums[cur], nums[left]
                left += 1
                cur += 1
            elif nums[cur] == 2:
                nums[right], nums[cur] = nums[cur], nums[right]
                right -= 1
            else:
                cur += 1
        return nums

法1：快排

必须掌握快排方法！！！

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        quickSort(0, n - 1, nums);
    }

    public void quickSort(int start, int end, int[] nums) {
        if (start >= end) {
            return;
        }
        int left = start, right = end;
        while (left < right) {
            while (nums[right] > nums[start] && left < right) {
                --right;
            }
            while (nums[left] <= nums[start] && left < right) {
                ++left;
            }
            if (left < right) {
                swap(left, right, nums);
            }
        }
        swap(start, right, nums);

        quickSort(start, left - 1, nums);
        quickSort(left + 1, end, nums);
    }

    public void swap(int left, int right, int[] nums) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

法2：三指针/荷兰国旗问题

思路还是很清晰的，多指针，一头一尾分别用来放置0和2
中间的指针则进行遍历，发现元素0则跟头指针交换元素，并各自加1，发现元素2则跟尾指针交换，尾指针减1

class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1, curInx = 0;
        while (curInx <= right) { // 注意这里需要有"="
            if (nums[curInx] == 0) {
                swap(left, curInx, nums);
                ++left;
                ++curInx;
            } else if (nums[curInx] == 2) {
                swap(right, curInx, nums);
                --right; // 交换过来的这个新的nums[curInx]还要继续进行鉴定
            } else {
                ++curInx;
            }
        }
    }

    public void swap(int i, int j, int[] nums) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}