题目
image.png
题解
题解1
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
sort(nums, 0, n-1);
}
private void sort(int[] nums, int l, int r){
int v = nums[l];
// nums[l+1, lt]<v, nums[lt+1, gt-1]=v, nums[gt,r]>v
int lt = l, gt = r+1, i=l+1;
while (i<gt){
if (nums[i]<v){
lt++;
swap(nums, lt, i);
i++;
}else if (nums[i]>v){
gt--;
swap(nums, gt, i);
}else i++;
}
swap(nums, l, lt); // nums[l,lt-1]<v, nums[lt,gt-1]=v, nums[gt,r]>v
if (l<=lt-1) sort(nums, l, lt-1); // l<lt-1
if (gt<=r) sort(nums, gt, r); // gt<r
}
private void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
