Leetcode 75.颜色分类

Leetcode 75.颜色分类

思路解析

考点：快排

计算复杂度

O(NlogN)
原理：
每次选arr[L:R] 中的1个arr[rand] 作为target, 然后与arr[R] 交换=> swap(arr, rand, R)
当arr[R] 在arr[L : R]所有元素中的排序越接近中间位置时，一次partition后把规模为N的原问题划分为两个子问题的规模越接近 N/2。用Master公式计算规模为 N/2的子问题的计算复杂度:

O(N) = T(N) = a*T(N/b) + O(N^d), a 取2(2个子问题), b取2(子问题规模为N/2), d取1(遍历 L~R，比较 arr[cur] 与target的大小及不同情况对应操作=>O(N)), 有 $lo{g}_{b}a=d$, 因此$O(N)=O(N\ast log{N}^d)=O(NlogN)$

空间复杂度

最好情况，target每次都取到在arr[L : R]所有元素中的排序的中位数，则logN深度的递归就能完成计算=>O(logN)

最差情况，target每次都取到在arr[L : R]所有元素中的排序的最大值或最小值，则lN深度的递归才能完成计算=>O(N)

三段partition

下图具体解释了 partition(int[] arr, int L, int R)的过程

子问题递归范围

通过oartition 获取到元素值==target的元素们——arr[(lessR + 1) : cur]，这部分元素们已经排好序，只需要递归对 arr[L: lessR] 和 arr[moreL: R] 排序, 直到递归基，再一层层quickSort3(arr, L, R)**返回到 quickSort3(arr, 0, arr.length - 1)**即完成排序

提交源码

class Solution {
    public void sortColors(int[] nums) {
        if(nums == null || nums.length < 2) return;

        quickSort3(nums, 0, nums.length - 1);
    }

    public static void quickSort3(int[] arr, int L, int R){
        if(L >= R) return;
        
        //select arr[rand] as  target
        swap(arr, L + (int) Math.random() * (R - L + 1), R);
        int[] idOfEqualRange = partition(arr, L, R);
        quickSort3(arr, L, idOfEqualRange[0] - 1);
        quickSort3(arr, idOfEqualRange[1] + 1, R);
    }

    public static int[] partition(int[] arr, int L, int R){  
        /*
        fun: partition of arr[L:R]
        return: id of equal range in arr[L:R] after partition --> {equalL, equalR}

        principle: arr[R] as target
        */
        if(L > R) return new int[]{-1, -1};
        if(L == R) return new int[] {L, R};

        //L < R
        int lessR = L - 1;
        int moreL = R;
        int cur = L;
        int target = arr[R];
        while(cur < moreL){
            if(arr[cur] < target) swap(arr, ++lessR, cur++);
            else if(arr[cur] == target) cur++;
            else swap(arr, --moreL, cur);  //! cur do not move
        }
        swap(arr, cur, R); // make sure: arr[:lessR] < target | == target | arr[moreL+1:] > target
        return new int[] {lessR + 1, cur};
        
    }

    public static void swap(int[] arr, int id1, int id2){
        int tmpt = arr[id1];
        arr[id1] = arr[id2];
        arr[id2] = tmpt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

视频教程

P99 体系学习班 快速排序之荷兰国旗

老师的源码：
https://github.com/algorithmzuo/algorithmbasic2020/blob/master/src/class05/Code02_PartitionAndQuickSort.java