LeetCode日记--75. Sort colors

碎碎念时间:好吧这是发烧那天做的题,一直没空写,就现在写一下吧。(对了吐槽一下天天快递,让我站在西南门等了快两小时,本来以为今晚可以把之前欠的Lc日记都写了,看起来是没希望了)。

题目如下

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Follow up:

Could you solve this problem without using the library's sort function?
Could you come up with a one-pass algorithm using only O(1) constant space?

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]


Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Example 3:

Input: nums = [0]
Output: [0]

Example 4:

Input: nums = [1]
Output: [1]

官方题解思路:

因为思维一直局限在用两个指针解决问题,我想了好久没想到啥好办法。

这道题是迪杰斯特拉提出的荷兰国旗问题,在大一开学C语言课的时候就有所耳闻,大概就是荷兰的三色国旗,(三色对应题目中的0,1,2),在不使用额外空间,不使用库排序函数的情况下,对其进行排序。

仔细想一下的话会发现,如果把某两种数按照要求排好了的话,剩下一种数的位置应该也是确定的。因此我们选择左右两个指针,分别表示数字0的右边解,还有数字2的左边界,把所有0和2按要求放好后,剩下的1也会在合适的位置上。

我们再设置一个cur指针,用来遍历当前数组,若nums[cur]==0,则cur位置的数字与左指针对应的数字互换;若等于2则反之。每次互换后边界指针继续向中间移动,直到leftPointer>rightPointer.

示意图(来自官方题解)

代码如下:

class Solution {
/*
  荷兰三色旗问题解
  */
  public void sortColors(int[] nums) {
    // 对于所有 idx < i : nums[idx < i] = 0
    // j是当前考虑元素的下标
    int p0 = 0, curr = 0;
    // 对于所有 idx > k : nums[idx > k] = 2
    int p2 = nums.length - 1;

    int tmp;
    while (curr <= p2) {
      if (nums[curr] == 0) {
        // 交换第 p0个和第curr个元素
        // i++,j++
        tmp = nums[p0];
        nums[p0++] = nums[curr];
        nums[curr++] = tmp;
      }
      else if (nums[curr] == 2) {
        // 交换第k个和第curr个元素
        // p2--
        tmp = nums[curr];
        nums[curr] = nums[p2];
        nums[p2--] = tmp;
      }
      else curr++;
    }
  }

}

复杂度分析:

总共遍历一次数组,时间复杂度是O(n),没有使用额外空间,空间复杂度为O(1)。

点赞

发表评论

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