1. 题目描述
题目中转:75. 颜色分类
2.详细题解
方法一:桶排序
只有三类颜色,按照指定颜色顺序排列,且原地排序,直使用桶排序算法。对于本题,先统计各颜色出现的频率,再按照指定颜色顺序,再原数组内存入相应的颜色,具体算法如下:
- Step1:初始化:颜色的顺序已经确定,直接建桶,由于各颜色使用数字 0 , 1 , 2 0,1,2 0,1,2表示,桶数据结构为数组,索引 i ( i < 3 ) i(i<3) i(i<3)处的数字即为该颜色出现的频率;原地数组排序的初始索引为 j = 0 j=0 j=0;
- Step2:遍历数组,根据颜色放入对应桶中,算法时间复杂度为 O ( n ) O(n) O(n);
- Step3:从左至右遍历桶,桶的索引为 i i i,值为 k k k,则在原数组 [ j : j + k ) [j:j+k) [j:j+k)中放入值 i i i;
- Step4:遍历结束,程序结束。
方法二:双指针
只有三类颜色,颜色 0 0 0和 2 2 2分别放入开头位置和结尾位置,因此可以使用双指针分别指向颜色 0 0 0和颜色 1 1 1,从左至右遍历数组,如果遇到颜色 0 0 0,则与左指针指向的值交换位置,如果遇到颜色 2 2 2,则与右指针指向的值交换位置。当遇到颜色 1 1 1时则不交换位置。
算法需要注意的细节是,对于左指针指向的值,一定不为颜色 2 2 2(因为左指针指向的位置<=遍历位置,如果能为 2 2 2,已经交换到尾部去了),对于右指针指向的值,可能为任意值,因此与遍历位置交换值后,该遍历位置还需要进行判断,并不能遍历下一个位置,否则会出现错误。
具体算法如下:
- Step1:初始化:两个指针 l e f t left left 和 r i g h t right right,分别指向数组的起始和结束位置;
- Step2:遍历指针未 i i i,初始指向起始位置;
- Step3:如果 n u m s [ i ] = = 2 nums[i] == 2 nums[i]==2且 i < = r i g h t i<=right i<=right,则交换 i i i和 r i g h t right right位置的值, r i g h t right right指针向左移动一位,即 r i g h t − − right-- right−−;
- Step4:重复步骤Step3,直至条件不成立;
- Step5:如果 n u m s [ i ] = = 0 nums[i]==0 nums[i]==0,则交换 i i i与 l e f t left left位置的值, l e f t left left指针向右移动一位,即 l e f t + + left++ left++;
- Step6:遍历指针 i i i向右移动一位, i + + i++ i++;
- Step7:条件 i < = r i g h t i<=right i<=right成立,则重复步骤Step3_Step6,否则到步骤Step8;
- Step8:程序结束。
3.代码实现
3.1 Python
方法一:桶排序
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
bucket = [0, 0, 0]
for num in nums:
bucket[num] += 1
j = 0
for i in range(3):
for _ in range(bucket[i]):
nums[j] = i
j += 1
方法二:双指针
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
left, right = 0, len(nums) - 1
i = 0
while i <= right:
while i <= right and nums[i] == 2:
nums[i], nums[right] = nums[right], nums[i]
right -= 1
if nums[i] == 0:
nums[i], nums[left] = nums[left], nums[i]
left += 1
i += 1
3.2 Java
方法一:桶排序
class Solution {
public void sortColors(int[] nums) {
int[] bucket = {0, 0, 0};
for (int num: nums){
bucket[num]++;
}
int j = 0;
for (int i=0; i < 3; i++){
for (int z=0; z < bucket[i]; z++){
nums[j++] = i;
}
}
}
}
方法二:双指针
class Solution {
public void sortColors(int[] nums) {
int left = 0, right = nums.length - 1;
int i = 0;
while (i <= right){
while (i <= right && nums[i] == 2){
int tmp = nums[i];
nums[i] = nums[right];
nums[right--] = tmp;
}
if (nums[i] == 0){
int tmp = nums[i];
nums[i] = nums[left];
nums[left++] = tmp;
}
i++;
}
}
}
执行用时不必过于纠结,对比可以发现,对于python和java完全相同的编写,java的时间一般是优于python的;至于编写的代码的执行用时击败多少对手,执行用时和网络环境、当前提交代码人数等均有关系,可以尝试完全相同的代码多次执行用时也不是完全相同,只要确保自己代码的算法时间复杂度满足相应要求即可,也可以通过点击分布图查看其它coder的code。