给定一个包含红色, 白色和蓝色, 一共 n 个元素的数组, 原地 https://baike.baidu.com/item/原地算法 对它们进行排序, 使得相同颜色的元素相邻, 并按照红色, 白色, 蓝色顺序排列.
此题中, 我们使用整数 0, 1 和 2 分别表示红色, 白色和蓝色.
注意:
不能使用代码库中的排序函数来解决这道题.
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶:
一个直观的解决方案是使用计数排序的两趟扫描算法. 首先, 迭代计算出 0,1 和 2 元素的个数, 然后按照 0,1,2 的排序, 重写当前数组. 你能想出一个仅使用常数空间的一趟扫描算法吗?
思路:
对数组只能进行一次扫描, 所以上面的做法可以否定, 又因为题目里一个数组只有三种数字 0,1,2 而 1 又是在数组的中间位置:
<1 1* >1, 这个是不是很类似于快速排序中的三路快排??
代码如下:
- class Solution {
- public void sortColors(int[] nums) {
- if (nums == null || nums.length == 0) {
- return;
- }
- int less = -1;
- int more = nums.length;
- int index = 0;
- while (index <more) {
- if (nums[index] < 1) {
- swap(nums, index, ++less);
- index++;
- continue;
- }
- if (nums[index]> 1) {
- swap(nums, index, --more);
- continue;
- }
- if (nums[index] == 1) {
- index++;
- }
- }
- }
- private void swap(int[] nums, int index, int more) {
- int tmp = nums[index];
- nums[index] = nums[more];
- nums[more] = tmp;
- }
- }
来源: http://www.bubuko.com/infodetail-2705557.html