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.
Here, we will use the integers 0
, 1
, and 2
to represent the color red, white, and blue respectively.
Follow up:
- Could you solve this problem without using the library's sort function?
- Could you come up with a one-pass algorithm using only
O(1)
constant space?
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]
Example 3:
Input: nums = [0] Output: [0]
Example 4:
Input: nums = [1] Output: [1]
思路:不是比较元素,是比较index。元素只要跟基准比较就行了。
中间的if不动了,此时还是left <= right。双方换一下
class Solution { public void sortColors(int[] nums) { int left = 0; int right = nums.length - 1; //和1比较 while (left <= right) { while (left < right && nums[left] < 1) { left++; } while (left <= right && nums[right] >= 1) { right--; } if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } //重设left right left = 0; right = nums.length - 1; //和2比较 while (left <= right) { while (left < right && nums[left] < 2) { left++; } while (left <= right && nums[right] >= 2) { right--; } if (left <= right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } } }View Code