Sort Colors
给一个数组, 由0,1,2组成, 让排序, 这个以为已经知道数组的元素个数. 是经典算法, 就是以1为pivot的quicksort的partition.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class Solution { public void sortColors(int[] nums) { int lt = 0; int gt = nums.length - 1; int k = lt; while(k <= gt) { if(nums[k] < 1) swap(nums, lt++,k++); else if(nums[k] > 1) swap(nums, gt--,k); else k++; } } public void swap(int[] nums, int i, int j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } |