题目描述

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

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

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

示例:

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

进阶:

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

https://leetcode-cn.com/problems/sort-colors/

解法1 – 桶排序 – O(n)

就像题目描述的直观方法那样,我们声明一个长度为3的数组,下标为0,1,2的位置分别记录0、1、2数字出现的次数。第一次扫描填充桶,第二遍扫描从桶里取数,回填到数组中。

时间复杂度O(n),准确的说是O(2*n);空间复杂度O(1)。全部代码如下:

class Solution {
    public void sortColors(int[] nums) {
        int[] buckets = new int[3];
        for (int num : nums)
            buckets[num]++;

        int idx = 0;
        for (int i = 0; i < buckets.length; i++) {
            while (buckets[i]-- > 0)
                nums[idx++] = i;
        }
    }
}

解法2 – Partition函数 – O(n)

记得快速排序的Partition函数吗?找一个pivot,两个指针指向数组两端,调用partition函数使得左边的元素都小于pivot;右边的元素都大于pivot。这里我们借用Partition函数的思想,用3个指针i、j、k。使得[0, i)的元素都是0、(j, |nums|)的元素都是2,而指针k扫描[0, |nums|)。

当k指向的当前元素是0,就把它与i所指的位置交换,然后i++;当k指向的当前元素是2,就把它与j所指的位置交换,然后j–;如果k指向的元素是1,那就k++。需要注意的是边界问题,k需要满足0<=i <=k <=j<|nums|。下面的条件k>=i实际上是限制i,如果我们不限制,就会使得i超越k,导致越界;对于变量j也是同理。

时间复杂度O(n),空间复杂度O(1)。全部代码如下:

class Solution {
    public void sortColors(int[] nums) {
        if (nums == null || nums.length < 2)
            return;
        int i = 0, j = nums.length - 1, k = 0;
        while (k < nums.length && k <= j) {
            int curr = nums[k];
            if (curr == 0 && k >= i) {
                int t = nums[i];
                nums[i++] = curr;
                nums[k] = t;
            } else if (curr == 2) {
                int t = nums[j];
                nums[j--] = curr;
                nums[k] = t;
            } else {
                k++;
            }
        }
    }
}
pwrliang Algorithms, Array, Partition, Sort

Leave a Reply

Your email address will not be published. Required fields are marked *