侧边栏壁纸
博主头像
阿里灰太狼博主等级

You have to believe in yourself . That's the secret of success.

  • 累计撰写 104 篇文章
  • 累计创建 50 个标签
  • 累计收到 12 条评论

目 录CONTENT

文章目录

leetcode-75. 颜色分类

阿里灰太狼
2022-03-24 / 0 评论 / 2 点赞 / 189 阅读 / 1,195 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-24,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

75. 颜色分类

JAVA解法

class Solution {
    public void sortColors(int[] nums) {
        // 获取数组长度
        int n = nums.length;
        // 定义两个指针的位置
        int p0 = 0, p1 = 0;
        // 开始遍历
        for (int i = 0; i < n; ++i) {
            // 当找到数字 1 时
            if (nums[i] == 1) {
                // 把 1 换到 p1 的位置
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                // 维护 p1
                ++p1;
                // 当找到数字 0 时
            } else if (nums[i] == 0) {
                // 把 0 换到 p0 的位置
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                // 若 p0 < p1 还得将此时 i 的位置与 p1 位置交换
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                // 同时维护 p0 和 p1
                ++p0;
                ++p1;
            }
        }
    }
}

题解分析

  这道题是「荷兰国旗问题」的典型题目,由计算机科学家 Edsger Wybe Dijkstra 首先提出。
  用一次遍历的话需要两个指针,先获取数组长度,定义两个指针 p0 和 p1 都指向第一个数,p0 是用来当找到 0 时进行交换的位置标记,同时维护 p0 和 p1 指针,同理 p1 则是用来当找到 1 时交换位置的标记,同时维护 p1 指针(疑惑:为什么这里 遇到 0 要维护两个指针,而遇到 1 只维护 p1 一个指针?接着往下看)。用 for 循环遍历数组,当遇到 0 或者 1 时,分别与标记位置进行交换,可用题目示例来举例,题目给的是 nums = [2,0,2,1,1,0],过程如表格所示:

i = 0

2 0 2 1 1 0
p0,p1,i

此时 i 所在位置的数为 2 无需任何操作。

i = 1

2 0 2 1 1 0
p0,p1 i

此时 i 所在位置的数为 0 ,则与 p0 进行交换,同时判断 p0 与 p1 的位置的先后,假如 p0 在 p1 后边的话还得再交换一次,即 i 所在位置的数与 p1 位置所在的数交换,在这里 p0 与 p1 指向的是同一个数,因此不用换,结果如下:

0 2 2 1 1 0
p1,p0,i

i = 2

0 2 2 1 1 0
p0,p1 i

此时 i 所在位置的数为 2 无需任何操作。

i = 3

0 2 2 1 1 0
p0,p1 i

此时 i 所在位置的数为 1 ,则与 p1 进行交换,结果如下:

0 1 2 2 1 0
p0 p1 i

在这里可以推一下,假如上边遇到 0 没有同时维护两个指针的话,这里就乱了,即使往后也没办法纠正,最后有个 1 位置错了,这就是为什么遇到 0 要同时维护两个指针的原因了。

i = 4

0 1 2 2 1 0
p0 p1 i

此时 i 所在位置的数为 1 ,则与 p1 进行交换,结果如下:

0 1 1 2 2 0
p0 p1 i

i = 5

0 1 1 2 2 0
p0 p1 i

此时 i 所在位置的数为 0 ,则与 p0 进行交换,同时这里满足 p0 在 p1 后边,还得再交换一次,即 i 所在位置的数与 p1 位置所在的数交换,结果如下:

0 0 1 1 2 2
p0 p1 i

这就是最终的结果了。

leetcode原题:75. 颜色分类

2

评论区