LeetCode 075 Sort Colors

LeetCode

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

n == nums.length 1 <= n <= 300
nums[i] is either 0, 1, or 2.

*Follow up: Could you come up with a one-pass algorithm using only constant extra space?

题目大意：

排序3值数组

算法思路：

类似于Quicksort的partition，但有三种值，需要有三个指针: left, i, right

注意事项：

1. 三个指针: left, i, right. 循环不是for每个元素，而是i <= right
2. nums[2]的时候，right要往前移
3. 和partition一样： nums[i] == 0，left和i都移动，nums[i] == 1只移动i

Python代码：

def sortColors(self, nums: List[int]) -> None:
	left, i, right = 0, 0, len(nums) - 1
	while i <= right: # remember
		if nums[i] == 0:
			nums[left], nums[i] = nums[i], nums[left]
			left += 1
			i += 1
		elif nums[i] == 1:
			i += 1
		else:
			nums[i], nums[right] = nums[right], nums[i]
			right -= 1 # remember

Java代码：

public void sortColors(int[] nums) {
	int middleStart = 0, middleEnd = nums.length-1, i=0;
	while(i<=middleEnd){
		if(nums[i]==2)
			swap(nums,i,middleEnd--);//no i++ coz 2,0,2,2, swap 2,2 and i can't +1
		else if(nums[i]==0)
			swap(nums,i++,middleStart++);
		else
			i++;
	}
			
}

public void swap(int[] a,int i,int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(1)