LeetCode 75. 颜色分类
原题链接
中等
作者:
罗那耳朵
,
2021-10-27 12:44:53
,
所有人可见
,
阅读 210
方法1, 从左到右
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
l = 0
r = n-1
i = 0
while i <= r:
if nums[i] == 0:
#交换到i位置的一定是1
nums[i], nums[l] = nums[l], nums[i]
l += 1
i += 1
elif nums[i] == 2:
#不确定交换到i位置的是哪个数字
nums[i], nums[r] = nums[r], nums[i]
r -= 1
else:
i += 1
方法2, 从右到左
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
l = 0
r = n -1
i = n-1
while i >= l:
if nums[i] == 2:
#交换到i位置的一定是1
nums[i], nums[r] = nums[r], nums[i]
i -= 1
r -= 1
elif nums[i] == 0:
#不确定交换到i位置的是哪个数字
nums[i], nums[l] = nums[l], nums[i]
l += 1
elif nums[i] == 1:
i -= 1