校招算法梳理(一)

| | | ℃ | 次阅读
字数: 2.8k | 阅读时长 ≈ 11

最近总想的是用一篇文章完成很多工作的总结，现在发觉有点不切实际了，还是一点点的来写吧！
排序算法之所以经典，主要是算法所体现的思想至关重要。
最近需要梳理一下校招面试算法的相关内容。
首先工程上基本不会使用的冒泡排序、选择排序，如何使用对数器测试算法的性能，还会着重整理递归行为的实质，以及插入排序、归并排序等算法及相关案例探究。所有的图片都是手绘的，真的挺难看…..果然还是没有艺术细胞。

衡量算法性能的标准

时间复杂度

具体来说，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分，如果记为f(N)，那么时间复杂度为O(f(N))

额外空间复杂度

有限变量能完成排序流程,包括辅助数组
冒泡排序在原数组上操作，则额外空间复杂度为O(1)

案例说明

有序数组A，无序数组B，请打印B中所有不在A中的数，A数组长度为N，B数组长度为M

  • 算法流程1：对于数组B中的每一个数，都在A中通过遍历的方式找一下；

    冒泡排序

  • 算法流程2：对于数组B中的每一个数，都在A中通过二分的方式找一下；

    先排序，再遍历比较，M*O(logN)

    二分搜索
    有序数组，从小到大排好序，在数组中搜索a，则需要O(logN)，即每次砍掉一半，可以砍log(2,N)次

  • 算法流程3：先把数组B排序，然后用类似外排的方式打印所有在A中出现的数；

    先排序MO(logM），再外排比较O(M+N)，整个复杂度MO(logM)+O(M+N)

    用两个指针移动去分别比较A/B数组各位置的大小，b<=a则停止。若等于，则不打印直接移动，除此之外都是a往下移动，谁小动谁。a和b有一个到末尾了就停。a最多指向M个数，b指向n个数，最坏情况O(M+N)

算法流程2和3分析：拼完指标拼常量

  • 如果A数组很短，M数组很大，即N很小，M大，则算法流程2性能更好，算法流程3中先对B排序耗费太大。

  • 如果B数组很短，A数组很长，则N大，M小，则需要确定具体的样本量，才能分析谁性能更好。

基本不用的排序：

冒泡排序

每次遍历比较相邻两个数的大小，并交换，第一圈最大的数来到最后的位置，可以排好一个数，依次下去排0—(n-2)位置上的数，依次下去即可。

额外空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
  for (int i = arr.length-1; i > 0 ;i--)
        {
//            第二圈遍历数组前面未排好序的数
            for (int j = 0; j < i; j++)
            {
                if(arr[j] > arr[j+1])
                {
                    swap(arr, j, j+1);
                }
            }
        }

选择排序

严格O(N^2)，额外空间复杂度O(1)

外层循环从0—(n-1)，固定0位置上的数，内层循环从1-n上依次与其比较大小，并选一个最小的数，记录其Index，交换到0位置上。再从1—(n-1)上遍历，固定1位置上的数，在2—n位置上选一个最小的数放在1位置上，依次下去即可。

内存循环遍历找到最小的数的下标。

1
2
3
4
5
6
7
for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
               minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }

常考的排序

插入排序

手上拿着排好序的牌，新拿一张牌，去和它之前的位置一路换，换不动就停并插入。插入排序的时间复杂度和数据状况有关系。

最好情况:O(N) 有序数组，每次只需要比较和他相邻的数，不用交换

最差情况:O(N^2) 逆序数组，每次都需要一次交换到底

平均情况:一般按最差情况估计算法

1
2
3
4
5
6
  for (int i = 1; i < arr.length; i++) {
//  与他前面的一个个的比
            for (int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--) {
                swap(arr, j, j+1);
            }
        }

对数器

贪心策略：证明自己的贪心策略是对的（不用数学证明，很难），用对数器去校验。

笔试前准备模板：二叉树随机样本生成器/堆/排序

  • 随机数组生成器

Math.random() 作出数组长度随机、值随机的数组

  • 绝对正确的方法

系统库调用

  • 大样本测试

50万组测试正确

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
49
50
51
52
53
54
public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

测试方法

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
public static void main(String[] args)
    {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;

        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);

            insertSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2))
            {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }

        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        insertSort(arr);
        printArray(arr);
    }

递归行为的实质

递归举例

比如数组求最大值，分治的思想，分为左右两个区域分别求最大值。什么情况下终止呢?L==R（代码写一下）

递归函数就是系统帮你压栈（就是系统栈），记录每一个过程的变量状态，但函数调子过程之前会把自己所有的过程全部压栈，信息完全保存，子过程返回之后会利用这些信息彻底还原现场继续跑，跑完再从栈中拿出一个函数，再还原现场，最终串起来所有子过程和父过程的通信。

任何递归行为都可以改成非递归，就是系统帮你压栈，自己压栈就是迭代。

如何分析递归行为的复杂度（主定理）

子过程代价+剩下过程的代价
适用范围：子过程问题规模一样，发生了n次(只看一步父问题划子问题)

范围之外只有bfprt算法在适用范围之外

归并排序

左侧排好，右侧排好，整体外排排好依次动，有一个到末尾了，剩下的拷贝进去辅助数组（merge），再整体拷贝回去原数组，整个排好序。

O(N*logN)，分治过程中只考虑规模，不考虑常数。左侧排好，右侧排好，merge的时候两个下标分别动，时间为O(N)。

额外空间复杂度O(N)，因为使用了辅助数组。T(N) = 2T(N/2)+O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//主函数入口
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr, 0, arr.length - 1);
}
//分治
public static void mergeSort(int[] arr, int l, int r) {
    if (l == r) {
        return;
    }
    int mid = l + ((r - l) >> 1);
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

Merge操作，左右侧都是有序的，如何让整体有序？

谁小填谁，填的数动，辅助数组也同时动，考虑边界条件，一个越界，另外一个不越界，需要把不越界剩下的数拷贝到辅助数组后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void merge(int[] arr, 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++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
    // 辅助数组拷贝回原数组
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
}

小和问题和逆序对问题

小和问题

在一个数组中，每一个数左边的比当前数小的数累加起来，叫做这个数的小和，求一个数组的小和。

  • 每一个位置都遍历其左边的数，找到比其小的数累加起来O(n^2)
  • 用归并排序做，merge的过程中求所有的小和，在merge的时候小组合并了，可以知道有多少数比current大，用数量分批的方式，集团合并，能起到加速的作用，而不是之前的遍历。一批一批，最终把范围扩到整体。

总体的小和=左侧部分产生的小和+右侧产生的小和+merge产生的小和

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
 public static int smallSum(int[] arr)
    {
        if (arr == null || arr.length < 2)
        {
            return 0;
        }
        return mergeSort(arr, 0, arr.length - 1);
    }

private static int mergeSort(int[] arr, int l, int r) {
    if (l == r)
    {
        return 0;
    }
    int m = l + ((r - l) >> 1);
    return mergeSort(arr, l,  m) + mergeSort(arr, m+1, r) + merge(arr, l, m, r);
}

private static int merge(int[] arr, int l, int m, int r) {
    int[] help = new int[r - l + 1];
    int i = 0;
    int p = l;
    int q = m + 1;
    int res = 0;

    //merge过程中算小数对和
    while (p <= m && q <= r)
    {
        res += arr[p] < arr[q] ? arr[p] * (r - q + 1) : 0;
        help[i++] = arr[p] < arr[q] ? arr[p++] : arr[q++];
    }
    while(p <= m)
    {
        help[i++] = arr[p++];
    }
    while(q <= r)
    {
        help[i++] = arr[q++];
    }
    for (i = 0; i < help.length; i++)
    {
        arr[l + i] = help[i];
    }
    return res;
}

逆序对问题

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

小结

归并排序快的原因，有序范围的区域合并的时候，不会浪费有序这个特点，永远是跨组比较，组内是有序的。而冒泡排序每次都会重复比较，浪费了很多比较。

代码细节&技巧

小细节：防止数组溢出的写法

1
2
3
mid=(L+R)/2 #可能溢出

mid=L+(R-L)/2 #L不溢出，R-L也不溢出，整体不溢出

位运算比算数运算快很多 ，虽然位运算和算数运算都是常数时间，但位运算的常数项会少很多，速度快。

-------------　　　　本文结束　　感谢您的阅读　　　　-------------
胡想成 wechat
欢迎关注个人公众号！
您的支持，是我装逼的最大动力！

本文标题:校招算法梳理(一)

文章作者:胡想成

发布时间:2019年08月21日 - 00:08

最后更新:2020年03月14日 - 10:03

原始链接:xchu.net/2019/08/21/算法/

版权声明:本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0许可协议,转载请注明出处！