【题目描述】
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
【示例】
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
【进阶】
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗?
代码实现
【解1】 看看就行啦 😁
func sortColors(_ nums: inout [Int]) {
var zero = 0,one = 0
for n in nums {
if n == 0 {
zero+=1
} else if n == 1 {
one+=1
}
}
let two = nums.count-zero-one
var i = 0
for _ in 0..<zero {
nums[i] = 0
i+=1
}
for _ in 0..<one {
nums[i] = 1
i+=1
}
for _ in 0..<two {
nums[i] = 2
i+=1
}
}
【解2】
思路:
1、使用三个指针来标识数组左边、右边和当前的index;
2、当nums[current]为0时,nums[left]和nums[current]交换,left++,current++;
3、当nums[current]为2时,nums[right]和nums[current]交换,right--;因为右边交换完后全是2,所以right--,跟左边全是0后left++一个道理,这里current不需要++,因为你不知道替换后的nums[current]是几;
4、当nums[current] == 1时,current++即可
5、时间复杂度O(n),空间复杂度O(1)
func sortColors(_ nums: inout [Int]) {
var left = 0,right = nums.count-1,current = 0
var tmp = 0
while current <= right {
if nums[current] == 0 {
tmp = nums[left]
nums[left] = nums[current]
nums[current] = tmp
current+=1
left+=1
} else if nums[current] == 2 {
tmp = nums[right]
nums[right] = nums[current]
nums[current] = tmp
right-=1
} else {
current+=1
}
}
}
网友评论