您现在的位置是:首页 >其他 >[Leetcode刷题] - LC075 Sort Colors网站首页其他

[Leetcode刷题] - LC075 Sort Colors

Ben土豆 2024-06-17 11:25:09
简介[Leetcode刷题] - LC075 Sort Colors

题目描述

一个随机序列包含0,1,2 在不占用额外内存的情况下将序列排序。

题目思路

1. 计数排序

计数排序思路比较简单,记录三个数字出现频率,然后根据频率将0,1,2重新加入数组,思路较为简单。

class Solution {
    public void sortColors(int[] nums) {
        // count sort
        int red = 0;
        int white = 0;
        int blue = 0;

        for (int i: nums) {
            if (i==0) red++;
            else if (i==2) blue++;
            else white++;
        }

        for (int i=0; i<nums.length; i++) {
            if (red!=0) {
                nums[i]=0;
                red--;
            } else if (white!=0) {
                nums[i]=1;
                white--;
            } else {
                nums[i]=2;
                blue--;
            }
        }


    }
}

时间复杂度:O(2N), 需要遍历两遍;空间复杂度:O(1)。 

2. 对向双指针 + 遍历指针

思路类似快速排序的partition算法,主要需要明确指针遍历时循环不变量,本题循环不变量可以定义为如下:(参考力扣)

循环不变量

定义p0 = 数字0的右边界,p1 = 数字1的右边界,p2 = 数字2的左边界

1. [0, p0) - 左闭右开区间内所有数字 == 0

2. [p0, p1) - 左闭右开区间所有数字 == 1

3. (p2, end] - 左开右闭区间内所有数字 == 2

引用: https://leetcode.cn/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/

 根据上述循环不变量条件,定义一个三个指针p0, p1, p2 来记录0,1,2的边界,我们可以验证一下这个循环不变量的正确性。

1. 初始时,p0=0, p1=0, p2=nums.length-1, 三个区间内没有值

2. 移动 p1 指针,如果[p0, p1]区间内发现 2,将p1 和 p2的值交换,这样[p2, end]依然满足都是2,可以将p2向左移动一步,但是[p0, p1]经过交换后并不确定是否是1,所以不能移动p1,要在下一次循环中检验

3. 同理,移动 p1 指针,如果[p0, p1]区间内发现 0,将p1 和 p0的值交换,这样[0, p0]依然满足都是0,可以将p0向右移动一步

4. 如果 p1 指针当前值是 1,那么证明[p0, p1]这部分依然满足都是1,p1向右移动一步

代码如下:

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p2 = nums.length-1;
        int p1=0;

        while(p1<nums.length) {
            if (p1<p2 && nums[p1]==2) {
                // if [p0, i] has 2 inside then move 2 to [p2, end]
                // since after swap, nums[p2] is 2, move p2 to p2-1 then check
                // since new nums[i] unknown need to check in next loop
                swap(nums, p1, p2);
                p2--;
            } else if (p1>=p0 && nums[p1]==0) {
                // if [p0, i] has 0 inside then move 0 to [0, p0]
                // after then nums[p0] is 0, move p0 to p0+1 then check
                // since new nums[i] unknown need to check in next loop
                swap(nums, p1, p0);
                p0++;
            } else {
                // if [p0, i] is 1, match move to next one
                p1++;
            }
        }
        
    }
        
    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
} 

 时间复杂度:O(N);空间复杂度:O(1)

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。