关注Java领域相关技术 记录有趣的事情

LeetCode-75. 颜色分类

US-B.Ralph
US-B.Ralph
2020-10-07

问题地址

LeetCode每日一题/2020-10-07

LeetCode75. 颜色分类


问题描述

规则

  • 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
  • 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:

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

示例

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

进阶

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

解析

解题思路

数据操作分析

  • 见思路分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现


官方解法

前言

  • 本题是经典的「荷兰国旗问题」,由计算机科学家 Edsger W. Dijkstra 首先提出。
  • 根据题目中的提示,我们可以统计出数组中 0,1,2 的个数,再根据它们的数量,重写整个数组。这种方法较为简单,也很容易想到,而本题解中会介绍两种基于指针进行交换的方法。

方法一:单指针

思路与算法

  • 我们可以考虑对数组进行两次遍历。在第一次遍历中,我们将数组中所有的 0 交换到数组的头部。在第二次遍历中,我们将数组中所有的 1 交换到头部的 0 之后。此时,所有的 2 都出现在数组的尾部,这样我们就完成了排序。
  • 具体地,我们使用一个指针 \textit{ptr} 表示「头部」的范围,\textit{ptr} 中存储了一个整数,表示数组 \textit{nums} 从位置 0 到位置 \textit{ptr}-1 都属于「头部」。\textit{ptr} 的初始值为 0,表示还没有数处于「头部」。
  • 在第一次遍历中,我们从左向右遍历整个数组,如果找到了 0,那么就需要将 0 与「头部」位置的元素进行交换,并将「头部」向后扩充一个位置。在遍历结束之后,所有的 0 都被交换到「头部」的范围,并且「头部」只包含 0。
  • 在第二次遍历中,我们从「头部」开始,从左向右遍历整个数组,如果找到了 1,那么就需要将 1 与「头部」位置的元素进行交换,并将「头部」向后扩充一个位置。在遍历结束之后,所有的 1 都被交换到「头部」的范围,并且都在 0 之后,此时 2 只出现在「头部」之外的位置,因此排序完成。

复杂度分析:

  1. 时间复杂度:O(n),其中 n 是数组 \textit{nums} 的长度。
  2. 空间复杂度:O(1)

编码实现

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
        for (int i = ptr; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }
}

方法二:双指针

思路及算法:

  • 方法一需要进行两次遍历,那么我们是否可以仅使用一次遍历呢?我们可以额外使用一个指针,即使用两个指针分别用来交换 0 和 1。
  • 具体地,我们用指针 p_0 来交换 0,p_1 来交换 1,初始值都为 0。当我们从左向右遍历整个数组时:
    • 如果找到了 1,那么将其与 \textit{nums}[p_1] 进行交换,并将 p_1 向后移动一个位置,这与方法一是相同的;
    • 如果找到了 0,那么将其与 \textit{nums}[p_0] 进行交换,并将 p_0 向后移动一个位置。这样做是正确的吗?我们可以注意到,因为连续的 0 之后是连续的 1,因此如果我们将 0 与 \textit{nums}[p_0] 进行交换,那么我们可能会把一个 1 交换出去。当 p_0 < p_1 时,我们已经将一些 1 连续地放在头部,此时一定会把一个 1 交换出去,导致答案错误。因此,如果 p_0 < p_1,那么我们需要再将 \textit{nums}[i]\textit{nums}[p_1] 进行交换,其中 i 是当前遍历到的位置,在进行了第一次交换后,\textit{nums}[i] 的值为 1,我们需要将这个 1 放到「头部」的末端。在最后,无论是否有 p_0 < p_1,我们需要将 p_0p_1 均向后移动一个位置,而不是仅将 p_0 向后移动一个位置。

复杂度分析:

  1. 时间复杂度:O(n),其中 n 是数组 \textit{nums} 的长度。
  2. 空间复杂度:O(1)

编码实现

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = temp;
                ++p1;
            } else if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                if (p0 < p1) {
                    temp = nums[i];
                    nums[i] = nums[p1];
                    nums[p1] = temp;
                }
                ++p0;
                ++p1;
            }
        }
    }
}

方法三:双指针

思路及算法:

  • 与方法二类似,我们也可以考虑使用指针 p_0 来交换 0,p_2 来交换 2。此时,p_0 的初始值仍然为 0,而 p_2 的初始值为 n-1。在遍历的过程中,我们需要找出所有的 0 交换至数组的头部,并且找出所有的 2 交换至数组的尾部。
  • 由于此时其中一个指针 p_2 是从右向左移动的,因此当我们在从左向右遍历整个数组时,如果遍历到的位置超过了 p_2 ,那么就可以直接停止遍历了。
  • 具体地,我们从左向右遍历整个数组,设当前遍历到的位置为 i,对应的元素为 \textit{nums}[i]
    • 如果找到了 0,那么与前面两种方法类似,将其与 \textit{nums}[p_0] 进行交换,并将 p_0 向后移动一个位置;
    • 如果找到了 2,那么将其与 \textit{nums}[p_2] 进行交换,并将 p_2 向前移动一个位置。
  • 这样做是正确的吗?可以发现,对于第二种情况,当我们将 \textit{nums}[i]\textit{nums}[p_2] 进行交换之后,新的 \textit{nums}[i] 可能仍然是 2,也可能是 0。然而此时我们已经结束了交换,开始遍历下一个元素 \textit{nums}[i+1],不会再考虑 \textit{nums}[i] 了,这样我们就会得到错误的答案。
  • 因此,当我们找到 2 时,我们需要不断地将其与 \textit{nums}[p_2] 进行交换,直到新的 \textit{nums}[i] 不为 2。此时,如果 \textit{nums}[i] 为 0,那么对应着第一种情况;如果 \textit{nums}[i] 为 1,那么就不需要进行任何后续的操作。

复杂度分析:

  1. 时间复杂度:O(n),其中 n 是数组 \textit{nums} 的长度。
  2. 空间复杂度:O(1)

编码实现

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; ++i) {
            while (i <= p2 && nums[i] == 2) {
                int temp = nums[i];
                nums[i] = nums[p2];
                nums[p2] = temp;
                --p2;
            }
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[p0];
                nums[p0] = temp;
                ++p0;
            }
        }
    }
}

精彩评论

跳转地址1:快速排序 partition(重点在设计循环不变量)

什么是 partition ?

思路:
  • 我们在学习 快速排序 的时候知道,可以选择一个标定元素(称为 pivot ,一般而言随机选择),然后通过一次扫描,把数组分成三个部分:
    • 第 1 部分严格小于 pivot 元素的值;
    • 第 2 部分恰好等于 pivot 元素的值;
    • 第 3 部分严格大于 pivot 元素的值。
  • 第 2 部分元素就是排好序以后它们应该在的位置,接下来只需要递归处理第 1 部分和第 3 部分的元素。
  • 经过一次扫描把整个数组分成 3 个部分,正好符合当前问题的场景。写对这道题的方法是:把循环不变量的定义作为注释写出来,然后再编码。

复习 partition

  • 说明:这部分与本题解法无直接关系,直接跳过不影响后续内容的阅读。
  • 下面的动画,从一个中间的状态开始演示,通过循环变量 i 以及设置两个边界变量 lt 和 gt 把一个数组分成 3 个部分。

  • 以下给出不同的写法,循环不变量的定义写在了注释中。使用「循环不变量」编码是为了便于我们处理细节,也方便他人阅读代码。

编码实现

循环不变量定义 1
  • 循环不变量:声明的变量在遍历的过程中需要保持定义不变。
  • 设计循环不变量的原则

    • 说明:设计循环不变量的原则是 不重不漏
      • len 是数组的长度;
      • 变量 zero 是前两个子区间的分界点,一个是闭区间,另一个就必须是开区间;
      • 变量 i 是循环变量,一般设置为开区间,表示 i 之前的元素是遍历过的;
      • two 是另一个分界线,我设计成闭区间。
  • 如果循环不变量定义如下:
    • 所有在子区间 [0, zero) 的元素都等于 0;
    • 所有在子区间 [zero, i) 的元素都等于 1;
    • 所有在子区间 [two, len – 1] 的元素都等于 2。
  • 于是编码要解决以下三个问题:
    • 变量初始化应该如何定义;
    • 在遍历的时候,是先加减还是先交换;
    • 什么时候循环终止。
  • 处理这三个问题,完全看循环不变量的定义。
    • 编码的时候,zero 和 two 初始化的值就应该保证上面的三个子区间全为空;
    • 在遍历的过程中,「下标先加减再交换」、还是「先交换再加减」就看初始化的时候变量在哪里;
    • 退出循环的条件也看上面定义的循环不变量,在 i == two 成立的时候,上面的三个子区间就正好 不重不漏 地覆盖了整个数组,并且给出的性质成立,题目的任务也就完成了。
  • 代码如下:

import java.util.Arrays;
public class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }
        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, len - 1] = 2

        // 循环终止条件是 i == two,那么循环可以继续的条件是 i < two
        // 为了保证初始化的时候 [0, zero) 为空,设置 zero = 0,
        // 所以下面遍历到 0 的时候,先交换,再加
        int zero = 0;

        // 为了保证初始化的时候 [two, len - 1] 为空,设置 two = len
        // 所以下面遍历到 2 的时候,先减,再交换
        int two = len;
        int i = 0;
        // 当 i == two 上面的三个子区间正好覆盖了全部数组
        // 因此,循环可以继续的条件是 i < two
        while (i < two) {
            if (nums[i] == 0) {
                swap(nums, i, zero);
                zero++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                two--;
                swap(nums, i, two);
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
  • 复杂度分析:
    • 时间复杂度:O(N),这里 N 是输入数组的长度;
    • 空间复杂度:O(1)
循环不变量定义 2
  • 代码如下:
public class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }
        // all in [0, zero] = 0
        // all in (zero, i) = 1
        // all in (two, len - 1] = 2

        // 为了保证初始化的时候 [0, zero] 为空,设置 zero = -1,
        // 所以下面遍历到 0 的时候,先加,再交换
        int zero = -1;

        // 为了保证初始化的时候 (two, len - 1] 为空,设置 two = len - 1
        // 所以下面遍历到 2 的时候,先交换,再减
        int two = len - 1;
        int i = 0;
        // 当 i == two 的时候,还有一个元素还没有看,
        // 因此,循环可以继续的条件是 i <= two
        while (i <= two) {
            if (nums[i] == 0) {
                zero++;
                swap(nums, i, zero);
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                swap(nums, i, two);
                two--;
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
  • 复杂度分析:
    • 时间复杂度:O(N),这里 N 是输入数组的长度;
    • 空间复杂度:O(1)
体会
  • 说明:这种做法是我在 Java 的 JDK 的源码中 Arrays.sort() 中学到的。
  • 我的体会是:
    • 编码者应该在代码中使用注释表达这段代码编写的算法思想,提醒自己也方便他人。
    • 但是源代码中类似 ++k = a[left – 1] 这样的代码建议不要写,会给阅读者带来理解上的障碍,这种做法也是《阿里巴巴 Java 开发手册》中不推荐的,理由是:变量的值发生变化是一个很重要的逻辑,应该单独成为一行,否则不利于调试和以后定位问题,这种语法糖我个人认为应该禁止使用。

相关问题

  • 下面这两个问题可以用于复习 partition 的过程。
  • 说明:这一题参与比较的是字符,题目中虽然没有给出字符的范围,但是通过测试可以知道,测试数据的字符不超过 128 个,符合有大量重复元素出现的情况,可以使用 partition 的过程对输入数据进行排序。

  • 「力扣」第 451 题参考代码:手写快速排序,如果很熟悉 partition,代码只需要稍作修改即可。

import java.util.Random;
public class Solution {
    private int[] freq;
    private static final Random RANDOM = new Random();
    public String frequencySort(String s) {
        // 先转换为字符数组,以避免 charAt() 方法每次都检查下标有效性
        char[] charArray = s.toCharArray();
        // 用 128 是测试出来的,说明题目中的字符只有 a-zA-Z
        freq = new int[128];
        for (char c : charArray) {
            freq[c]++;
        }

        int len = charArray.length;
        quickSort(charArray, 0, len - 1);
        return new String(charArray);
    }

    private void quickSort(char[] charArray, int left, int right) {
        if (left >= right) {
            return;
        }
        int randomIndex = left + RANDOM.nextInt(right - left + 1);
        swap(charArray, randomIndex, left);

        // 循环不变量定义
        // all in [left + 1, lt] 的频数 > pivot 的频数
        // all in [lt + 1, i) 的频数 = pivot 的频数
        // all in [gt, right] 的频数 < pivot 的频数
        int pivot = charArray[left];
        int lt = left;
        int gt = right + 1;

        int i = left + 1;
        while (i < gt) {
            // 只需要在这句话外面套一层 freq [] ,其它逻辑和快速排序一样
            if (freq[charArray[i]] > freq[pivot]) {
                lt++;
                swap(charArray, i, lt);
                i++;
            } else if (charArray[i] == pivot) {
                i++;
            } else {
                gt--;
                swap(charArray, i, gt);
            }
        }
        swap(charArray, left, lt);
        // 注意这里,大大减少了分治的区间
        quickSort(charArray, left, lt - 1);
        quickSort(charArray, gt, right);
    }

    private void swap(char[] charArray, int index1, int index2) {
        char temp = charArray[index1];
        charArray[index1] = charArray[index2];
        charArray[index2] = temp;
    }
}

参考资料

  • 在《算法导论》里大量使用了「循环不变量」这个概念说明和证明问题。但「循环不变量」并不是一个很高深的概念,其实我们很多时候,在编写代码的过程中都在不自觉地维护了变量的定义。「循环不变量」只是一个学术化的名字而已,设计清楚「循环不变量」,可以帮助我们写出正确的代码。
    • 《算法导论》第 2.1 节 插入排序
    • 《算法导论》第 2.3.1 节分治法
    • 《算法导论》第 6.3 节 建堆
    • 《算法导论》第 7.1 节 快速排序的描述
  • 事实上,一个广泛应用「循环不变量」概念的算法就是 二分查找,二分查找有些时候不能写对,与不能维持循环不变量的定义有很大的关系。
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

1 × 2 =