[Leetcode][第75题][JAVA][颜色分类][双（三）指针][计数排序]

【问题描述】[中等]

【解答思路】

1. 三指针

时间复杂度：O(N) 空间复杂度：O(1)

class Solution { public void sortColors(int[] nums) { int n = nums.length; int p0 = 0, p2 = n - 1; for (int i = 0; i <= p2; ++i) { while (i <= p2 && nums[i] == 2) { int temp = nums[i]; nums[i] = nums[p2]; nums[p2] = temp; --p2; } if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[p0]; nums[p0] = temp; ++p0; } } } } public void sortColors(int[] nums) { int len= nums.length; int low = 0 ; int high= len-1; int i=0; while(i<=high){ if(nums[i]==0){ int tmp = nums[i]; nums[i] = nums[low]; nums[low] =tmp; ++i; ++low; }else if(nums[i]==1){ ++i; }else if(i<=high && nums[i]==2){ int tmp = nums[i]; nums[i] = nums[high]; nums[high] =tmp; --high; } } }

快排思想理解

import java.util.Arrays; public class Solution { public void sortColors(int[] nums) { int len = nums.length; if (len < 2) { return; } // all in [0, zero) = 0 // all in [zero, i) = 1 // all in [two, len - 1] = 2 // 循环终止条件是 i == two，那么循环可以继续的条件是 i < two // 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0， // 所以下面遍历到 0 的时候，先交换，再加 int zero = 0; // 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len // 所以下面遍历到 2 的时候，先减，再交换 int two = len; int i = 0; // 当 i == two 上面的三个子区间正好覆盖了全部数组 // 因此，循环可以继续的条件是 i < two while (i < two) { if (nums[i] == 0) { swap(nums, i, zero); zero++; i++; } else if (nums[i] == 1) { i++; } else { two--; swap(nums, i, two); } } } private void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } } 作者：liweiwei1419 链接：https://leetcode-cn.com/problems/sort-colors/solution/kuai-su-pai-xu-partition-guo-cheng-she-ji-xun-huan/

2. 单指针 两次循环

时间复杂度：O(N) 空间复杂度：O(1)

class Solution { public void sortColors(int[] nums) { int n = nums.length; int ptr = 0; for (int i = 0; i < n; ++i) { if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = temp; ++ptr; } } for (int i = ptr; i < n; ++i) { if (nums[i] == 1) { int temp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = temp; ++ptr; } } } }

【总结】

1. 双指针三指针 有序排序重要思想

2.循环不变量

转载链接：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/