校招算法梳理(一)

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

衡量算法性能的标准

时间复杂度

具体来说,在常数操作数量的表达式中,只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分,如果记为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许可协议,转载请注明出处!