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

本文主要是介绍【重点】【三指针】【荷兰国旗问题】【快排】75.颜色分类，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

法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;}
}