75. 颜色分类

75. 颜色分类

双指针——快慢指针

class Solution {public void sortColors(int[] nums) {int n = nums.length;int p0 = 0;for(int i = 0; i < n; i++){if(nums[i] == 0){swap(nums, p0, i);p0++;}}int p1 = p0;for(int i = p0; i < n; i++){if(nums[i] == 1){swap(nums, p1, i);p1++;}}}void swap(int[] nums, int x, int y){int tmp = nums[x];nums[x] = nums[y];nums[y] = tmp;}
}

一次遍历

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