Leetcode算法Java全解答--75. 颜色分类.md

Posted by lizhao on 07-09,2019

Leetcode算法Java全解答--75. 颜色分类

[toc]

题目

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意: 不能使用代码库中的排序函数来解决这道题。

进阶:

一个直观的解决方案是使用计数排序的两趟扫描算法。 首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗?


示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

想法

遍历数组,同时拥有三个游标

left游标用来表示0的分界点(左边都是0),right游标用来表示2的分界点(右边都是2)

tmp游标表示正在游走的指针

当遇到数字2的时候,就将tmp和right的值交换,这时候right值为2,所以就把right往前移一位

当遇到数字0的时候,就将tmp和left的值交换,这时候left值为0,所以就把left往前移一位,同时tmp肯定不为2,所以往后移一位

当遇到数字0的时候,就将tmp++;

执行过程:

arr =  [2, 0, 2, 1, 1, 0],left = 0,right = 5,tmp = 0
第一轮:arr[tmp] == 2   >>  swap(arr[tmp],swap[right])  >> [0, 0, 2, 1, 1, 2],left = 0,right = 4,tmp = 0
第二轮:arr[tmp] == 0   >>  swap(arr[tmp],swap[left])  >> [0, 0, 2, 1, 1, 2],left = 1,right = 4,tmp = 1
第三轮:arr[tmp] == 0   >>  swap(arr[tmp],swap[left])  >> [0, 0, 2, 1, 1, 2],left = 2,right = 4,tmp = 2
第四轮:arr[tmp] == 2   >>  swap(arr[tmp],swap[right])  >> [0, 0, 2, 1, 1, 2],left = 2,right = 3,tmp = 2

结果

超过78%的测试案例

时间复杂度/空间复杂度:n/n

总结

代码

我的答案

public void sortColors(int[] nums) {
    int leftIndex = 0;
    int rightIndex = nums.length - 1;
    int tmpIndex = 0;
    // 0、2的时候进行交换
    while (tmpIndex < rightIndex) {
        int num = nums[tmpIndex];
        if (num == 1) {
            tmpIndex++;
        }
        if (num == 0) {
            swapArrByIndex(nums, tmpIndex, leftIndex);
            leftIndex++;
            tmpIndex++;
        }
        if (num == 2) {
            swapArrByIndex(nums, tmpIndex, rightIndex);
            rightIndex--;
        }
    }

}
private static void swapArrByIndex(int[] arr, int index1, int index2) {
    int tmp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = tmp;
}

大佬们的答案

/**************************************
 * 比我好的答案 better
 * 二次遍历法
 * ***********************************/
public void better(int[] nums) {
    int a = 0, b = 0, c = 0;
    for (int n : nums) {
        if (n == 0) {
            a++;
        } else if (n == 1) {
            b++;
        } else if (n == 2) {
            c++;
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (a != 0) {
            nums[i] = 0;
            a--;
        } else if (b != 0) {
            nums[i] = 1;
            b--;
        } else if (c != 0) {
            nums[i] = 2;
            c--;
        }
    }
}

测试用例

@Test
public void test075() {
    // 创建测试案例

    int[] arr1 = new int[] { 2, 0, 2, 1, 1, 0 };

    // 测试案例期望值
    int[] expResult1 = new int[] { 0, 0, 1, 1, 2, 2 };

    // 执行方法
    Solution075 solution075 = new Solution075();
    solution075.sortColors(arr1);

    // 判断期望值与实际值
    Assert.assertEquals(expResult1, arr1);
}

其他

代码托管码云地址:https://gitee.com/lizhaoandroid/LeetCodeAll.git

查看其他内容可以点击专栏或者我的博客哈:https://blog.csdn.net/cmqwan

“大佬们的答案” 标签来自leetcode,侵权请联系我进行删改

如有疑问请联系,联系方式:QQ3060507060