image.png
方法一：排序法
class Solution {
public void sortColors(int[] nums) {
Arrays.sort(nums);
}
}
时间复杂度O(nlogn)
空间复杂度O(1)
方法二：双指针法
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int p0 =0, p1 =0;
for(int i =0 ;i<n ;i++){
if(nums[i]==1){
int temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
p1++;
}else if(nums[i]==0){
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
if(p0<p1){
temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
}
p0++;
p1++;
}
}
}
}
时间复杂度：O(n)
空间复杂度：O（1）
