颜色分类 ---- 分治-快排

本文主要是介绍颜色分类 ---- 分治-快排，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题目:

分析:

• 运用将"数组分成三块"的思想:
  • 需要定义三个指针:
    left指向最左侧的区域的最右边, 所以left起始为-1
    right指向最右侧色区域的最左边, 所以right起始为nums.length
    i用来遍历数组
  • 这三个指针就将数组分成了四块
    [0,left] 为0
    [left + 1, i] 为1
    [i, right - 1] 为还没有判断的数
    [right, nums.length - 1] 为2
    
  • i从头开始遍历, 一共有三种情况:
    第一种情况:
    nums[i] == 0, 满足左边的区域, 所以将left++, 交换nums[i]和nums[left], 此时交换过来的值一定是已经判断完的, 所以i++
    第二种情况:
    nums[i] == 1, 满足中间的区域, 不需要做交换, 直接让i++
    第三种情况:
    nums[i] == 2, 满足最右边的区域, 此时让right--, 交换nums[i]和nums[right], 此时交换过来的数据是还没有判断的, 所以i不能++

代码:

class Solution {public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}public void sortColors(int[] nums) {int left = -1;int right = nums.length;int i = 0;while (i < right) {if (nums[i] == 0) {swap(nums, i++, ++left);} else if (nums[i] == 1) {i++;} else {swap(nums, i, --right);}}}
}

这篇关于颜色分类 ---- 分治-快排的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---