Leetcode # 75 (Python): Sort Colors
Sort Colors
- Difficulty: Medium
- Type: Sorting
- link
Problem
- Difficulty: Medium
- Type: Sorting
- link
Solution
- Dutch National Flag Problem (Three Pointers)
- Time complexity: O(n)
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# mid value equals 1 in this problem
start = 0
cur = 0
end = len(nums)
while cur < end:
# Swap with the start pointer when value in current pointer is smaller than mid
if nums[cur] < 1:
nums[start], nums[cur] = nums[cur], nums[start]
start += 1
cur += 1
# Swap with the end pointer when value in current pointer is bigger than mid
elif nums[cur] > 1: # mid
end -= 1
nums[cur], nums[end] = nums[end], nums[cur]
# Do not swap but increase current pointer by 1 if value in cur pointer = mid
else:
cur += 1
Author And Source
이 문제에 관하여(Leetcode # 75 (Python): Sort Colors), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ahn16/Leetcode-75-Python-Sort-Colors저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)