题目链接:力扣
解题思路:因为整个nums数组中只有0,1,2三个数组成。对nums升序排序后,0一定都在数组的最左边,2一定都在数组的最右边,1在数组的中间。那么只需要将0移动到数组的左边,2移动到数组的右边,当前1和2全部移动完成后。剩下的1就在数组中间了。所以可以使用两个指针标记已经排序好的0和2。
常用空间的一趟扫描算法如下:
- left = 0:标记下一个0待放入的位置
- right = num.length-1:标记下一个2待放入的位置
- 从前往后遍历nums数组,直到i>right:
- 如果nums[i] == 0:需要将这个0移动到数组的左边
- tem = nums[left]
- nums[left] = nums[i]
- nums[i] = tem
- left++
- 如果 nums[i] == 2:需要将这个0移动到数组的右边
- tem = nums[right]
- nums[right] = nums[i]
- nums[i] = tem
- right --
- continue:这里continue,不让 i 进行加1操作,因为交换后 nums[i]这个位置的数组可能为1,这个时候,需要下次循环中继续处理这个数组,将其移动到数组的左边
- i ++
- 如果nums[i] == 0:需要将这个0移动到数组的左边
AC代码:
class Solution {public static void sortColors(int[] nums) {int left = 0;int right = nums.length - 1;for (int i = 0; i <= right; ) {if (nums[i] == 0) {int tem = nums[left];nums[left] = nums[i];nums[i] = tem;left++;} else if (nums[i] == 2) {int tem = nums[right];nums[right] = nums[i];nums[i] = tem;right--;continue;}i++;}}
}