NO.75 颜色分类 中等
思路一：计数排序
看完题感觉就是个排序，题干里也说了直观的方法就是计数排序。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public void sortColors(int[] nums) {
int[] counter=new int[3];
for (int num : nums) {
counter[num]++;
}
int idx=0;
for (int i=0;i<counter.length;i++) {
while (counter[i]-- > 0) {
nums[idx++]=i;
}
}
}
|
时间复杂度：O(n)
思路二：快速排序
用类似于简化三路快排的方式进行排序。用curr指向当前遍历元素，left指向左边放0的的位置，right指向右边放2的位置。
curr去进行遍历，遇到0交换到左边部分，遇到1继续遍历，遇到2交换到右边部分。保持left指向左边放0的部分的后一个位置，right指向右边放2的部分的前一个位置。直至curr>right结束遍历，就将数组按照0、1、2的顺序分成了三部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public void sortColors(int[] nums) {
int left=0,right=nums.length-1,curr=0;
while (curr <= right) {
if (nums[curr] == 0) {
swap(nums,left,curr);
left++;
curr++;
} else if (nums[curr] == 1) {
curr++;
} else if (nums[curr] == 2) {
swap(nums,curr,right);
right--;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
|
时间复杂度：O(n)
本人菜鸟，有错误请告知，感激不尽！
更多题解和源码:github