栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

左程云算法笔记(二)递归、mergeSort、荷兰国旗、快排

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

左程云算法笔记(二)递归、mergeSort、荷兰国旗、快排

左程云算法笔记(二)
    • 递归的复杂度分析
          • master公式
    • 归并排序及相关问题
          • 1. 归并排序
          • 2. 小和问题 (牛客cd21)
          • 3. 逆序对问题 (LC-剑指51)
    • 快速排序及相关问题
          • 荷兰国旗1.0
          • 荷兰国旗2.0 (LC75)
          • 快排1.0
          • 快排2.0
          • 快排3.0 (随机快速排序)

递归的复杂度分析 master公式

符合子问题为等规模递归的情况可用master公式求解时间复杂度

T ( N ) = a ( N b ) + f ( N ) T(N) = a(frac{N}{b}) + f(N) T(N)=a(bN​)+f(N)
其中, a a a表示递归的次数也就是生成的子问题数, b b b表示每次的子问题是原问题的 1 b frac{1}{b} b1​规模, f ( N ) f(N) f(N)表示分解和合并所要花费的时间之和(除了子以外需要的时间复杂度)

若 l o g b a < d log_b a < d logb​a 若 l o g b a = d log_b a = d logb​a=d, 则时间复杂度为 O ( N d l o g N ) O(N^d logN) O(NdlogN)
若 l o g b a > d log_b a > d logb​a>d, 则时间复杂度为 O ( N l o g b a ) O(N^{log_b a}) O(Nlogb​a)

归并排序及相关问题 1. 归并排序

归并排序是分治算法的一个典型应用。首先将原数组拆分成多个不相交的子数组,对每个子数组排序,然后将有序子数组合并,合并过程中确保合并后的子数组仍然有序。合并结束之后,整个数组排序结束。

[ 6 , 2 , 7 , 1 , 3 , 0 , 8 , 9 , 5 , 4 ] [6, 2, 7, 1, 3, 0, 8, 9, 5, 4] [6,2,7,1,3,0,8,9,5,4]自顶向下

数组拆分情况如下。

[ [ 6 , 2 , 7 , 1 , 3 ] , [ 0 , 8 , 9 , 5 , 4 ] ] [[6, 2, 7, 1, 3], [0, 8, 9, 5, 4]] [[6,2,7,1,3],[0,8,9,5,4]]

[ [ [ 6 , 2 , 7 ] , [ 1 , 3 ] ] , [ [ 0 , 8 , 9 ] , [ 5 , 4 ] ] ] [[[6, 2, 7], [1, 3]], [[0, 8, 9], [5, 4]]] [[[6,2,7],[1,3]],[[0,8,9],[5,4]]]

[ [ [ [ 6 , 2 ] , [ 7 ] ] , [ [ 1 ] , [ 3 ] ] ] , [ [ [ 0 , 8 ] , [ 9 ] ] , [ [ 5 ] , [ 4 ] ] ] ] [[[[6, 2], [7]], [[1], [3]]], [[[0, 8], [9]], [[5], [4]]]] [[[[6,2],[7]],[[1],[3]]],[[[0,8],[9]],[[5],[4]]]]

[ [ [ [ [ 6 ] , [ 2 ] ] , [ 7 ] ] , [ [ 1 ] , [ 3 ] ] ] , [ [ [ [ 0 ] , [ 8 ] ] , [ 9 ] ] , [ [ 5 ] , [ 4 ] ] ] ] [[[[[6], [2]], [7]], [[1], [3]]], [[[[0], [8]], [9]], [[5], [4]]]] [[[[[6],[2]],[7]],[[1],[3]]],[[[[0],[8]],[9]],[[5],[4]]]]

数组归并情况如下。

[ [ [ [ 2 , 6 ] , [ 7 ] ] , [ 1 , 3 ] ] , [ [ [ 0 , 8 ] , [ 9 ] ] , [ 4 , 5 ] ] ] [[[[2, 6], [7]], [1, 3]], [[[0, 8], [9]], [4, 5]]] [[[[2,6],[7]],[1,3]],[[[0,8],[9]],[4,5]]]

[ [ [ 2 , 6 , 7 ] , [ 1 , 3 ] ] , [ [ 0 , 8 , 9 ] , [ 4 , 5 ] ] ] [[[2, 6, 7], [1, 3]], [[0, 8, 9], [4, 5]]] [[[2,6,7],[1,3]],[[0,8,9],[4,5]]]

[ [ 1 , 2 , 3 , 6 , 7 ] , [ 0 , 4 , 5 , 8 , 9 ] ] [[1, 2, 3, 6, 7], [0, 4, 5, 8, 9]] [[1,2,3,6,7],[0,4,5,8,9]]

[ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0,1,2,3,4,5,6,7,8,9]

public int[] mergeSort(int[] nums) {
        process(nums, 0, nums.length-1);
        return nums;
}

public void process(int[] nums, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R-L)>>1);
        process(nums, L, mid);
        process(nums, mid+1, R);
        merge(nums, L, mid, R);
}

public void merge(int[] nums, int L, int M, int R) {
        int[] help = new int[R-L+1];
        int i=0;
        int p1 = L;
        int p2 = M+1;
        while (p1 <= M && p2 <= R) {
            help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        // 下面两个while loop只会中一个
        while (p1 <= M) {
            help[i++] = nums[p1++];
        }
        while (p2 <= R) {
            help[i++] = nums[p2++];
        }
        
        for (int j=0; j 

mergeSort将时间复杂度从 O ( N 2 ) O(N^2) O(N2)降为 O ( N l o g N ) O(NlogN) O(NlogN)是因为:相比于冒泡、插排、选排每轮比较只能确定一个数的位置,mergeSort中每次比较都不会浪费信息,而是合并成一个有序的数组,内部不会进行重复比较

2. 小和问题 (牛客cd21)

在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。
e.g. 数组 s = [ 1 , 3 , 5 , 2 , 4 , 6 ] s=[1,3,5,2,4,6] s=[1,3,5,2,4,6], s[0]左边没有比它小的数字,s[1]左边比它小的数字是1,s[2]左边比它小的数字的和为1+3=4,s[3] 左边比它小的数字是1… 数组s的小和为 1+(1+3)+1+(1+3+2)+(1+3+5+2+4+6)=27

思路:

  1. “这个数左边比它小的数字的和” 等同于 “这个数右边有几个数比它大,这个数就会被计算进几次小和,就把这个数乘几次”
  2. 利用归并排序中的merge步骤计算小和,可以将复杂度从 O ( N 2 ) O(N^2) O(N2)改进为 O ( N l o g N ) O(NlogN) O(NlogN)。同时,利用merge时并入的两个序列分别有序的特性可以省去不必要的比较,如[134]并入[25]时,2>1直接推出2后面的数都>1,因此直接+=1*(endIndex-indexOf(2)+1)即可。

为什么利用mergeSort既不会重复也不会漏算?
比如,对于数组 [1,3,4,2,5],1会依次和3比较,组成[1,3]; 再与4比较,组成 [1,3,4]; 再与 [2,5]比较,组成[1,2,3,4,5]。[1,3,4]内部不会重复比较,同时1也会与每一个其右边的数字分别进行比较,不会遗漏。

public static long smallSum(int[] nums) {
        return process(nums, 0, nums.length-1);
}

public static long process(int[] nums, int L, int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + ((R-L)>>1);
        return process(nums, L, mid) +
               process(nums, mid+1, R) +
               merge(nums, L, mid, R);
}

public static long merge(int[] nums, int L, int M, int R) {
        int[] help = new int[R-L+1];
        int p1 = L;
        int p2 = M+1;
        int i = 0;
        long res = 0;
        while (p1<= M && p2<= R) {
            if (nums[p1] <= nums[p2]) { // 牛客网这题中小和的定义是左边<=该数的和,按原来题意改为<即可
                res += (R-p2+1) * nums[p1];
                help[i++] = nums[p1++];
            } else {
                help[i++] = nums[p2++];
            }            
        }
        while (p1<=M) {
            help[i++] = nums[p1++];
        }
        while (p2<=R) {
            help[i++] = nums[p2++];
        }
        
        for (int j=0; j 
3. 逆序对问题 (LC-剑指51) 

在数组中的两个数字,如果左边的数字大于右边的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
思路和小和问题基本一致,只要将数组用mergeSort倒序排序即可

public int reversePairs(int[] nums) {
    return process(nums, 0, nums.length-1);
}

public int process(int[] nums, int L, int R) {
    if (L >= R) { // for nums=[]
        return 0;
    }
    int mid = L + ((R-L) >> 1);
    return process(nums, L, mid) +
           process(nums, mid+1, R) +
           merge(nums, L, mid, R);
}

public int merge(int[] nums, int L, int M, int R) {
    int[] help = new int[R-L+1];
    int pair = 0;
    int p1 = L;
    int p2 = M+1;
    int i = 0;
    while (p1<= M && p2<= R) {
        if (nums[p1] > nums[p2]) {
            pair += R-p2+1;
            help[i++] = nums[p1++];
        } else {
            help[i++] = nums[p2++];
        }
    }
    while (p1<= M) {
        help[i++] = nums[p1++];
    }
    while (p2<= R) {
        help[i++] = nums[p2++];
    }
    for (int j=0; j 
快速排序及相关问题 
荷兰国旗1.0 

给定一个数组arr,和一个数num。把<=num的数放在数组的左边, >num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(1)。

思路:单指针记录<=num的范围 (start from -1)。

  • 若arr[i] <= num,则arr[i]和<=区域的下一个数字作交换,<=区右扩,i++。
  • 若arr[i]>num,则直接i++。
public void sortColors(int[] nums, int pivot) {
        int i=0;
        int left = -1;
        while (i <= nums.length-1) {
            if (nums[i]  
荷兰国旗2.0 (LC75) 

给定一个数组arr,和一个数num。把num的数放在数组的右边。要求额外空间复杂度O(1),时间复杂度O(1)。

思路:
双指针,一个记录num的范围 (start from arr.length)。

  • 若arr[i]
  • 若arr[i]=num,直接i++ (即扩充=区)。
  • 若arr[i]>num,arr[i]和>区域的前一个数字作交换,>区左扩,i不变 (因为换上来的数字还没有被检查过)。
public void sortColors(int[] nums, int pivot) {
        int i=0;
        int left = -1;
        int right = nums.length;
        while (i < right) {
            if (nums[i] < pivot) {
                swap(nums, ++left, i++);
            } else if (nums[i] > pivot) {
                swap(nums, --right, i);
            } else {
                i++;
            }
        }
}

public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
}
快排1.0

将arr最后一个数视为num,对arr进行荷兰国旗1.0操作,即分区。再对于分区后的两个子数组进行重复操作(递归),直至子数组的长度不超过 1 时,不需要继续分区。

快排2.0

对arr进行荷兰国旗2.0操作。快排2.0会稍快于快排1.0,因为中间==num的部分已经确定了位置不用再动了。
快排1.0和2.0版本时间复杂度都是 O ( N 2 ) O(N^2) O(N2),因为存在最差情况如[1,2,3,4,5,6,7,8,9],每次partition只搞定一个数。
同理,快排1.0和2.0版本的空间复杂度是O(N):考虑最差情况需要产生n个递归栈。

快排3.0 (随机快速排序)

如能使num的选择都不偏,则 T ( N ) = 2 ( N 2 ) + O ( N ) T(N)=2(frac{N}{2})+O(N) T(N)=2(2N​)+O(N),得到O(NlogN)的时间复杂度。
快排3.0中每次随机选一个数作划分值,好情况、坏情况是等概率的,时间复杂度为O(NlogN) (用数学期望等知识证明)

public int[] quickSort(int[] nums) {
    partition(nums, 0, nums.length-1);
    return nums;
}

public int[] sortColors(int[] nums, int pivot, int L, int R) {
    int less = L-1;
    int more = R+1;
    int i=L;
    while (i pivot) {
            swap1(nums, i, --more);
        } else {
            i++;
        }
    }
    return new int[] {less+1, more-1};
}

public void partition(int[] nums, int L, int R) {
    if (L >= R) {
        return;
    }
    int pivot = (int) (Math.random() * (R-L+1) + L);
    int[] equalArea = sortColors(nums, nums[pivot], L, R);
    partition(nums, L, equalArea[0]-1);
    partition(nums, equalArea[1]+1, R);
}

同理,随机快排的空间复杂度是O(logN):平均状态下pivot在arr中间,递归栈最深为logN级别

Reference:
leetcode讲解-stormsunshine
小和问题和逆序对问题
第二课:荷兰国旗问题,快速排序,堆排序,排序算法的稳定性,桶排序

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950561.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号