编程之美|编程之美 2.10找数组中的最大值和最小值
Q: 对于一个由N个整数数组，需要比较多少次才能把最大和最小的数找出来呢？
A: 这个还算是比较容易，遍历一次，就可以找出最大值和最小值，把他们当做是两个单独的事件来进行处理，O(2n)的时间复杂度；
Scheme0：寻找数组中的最大值和最小值看成是两个独立的问题，对它们分别求解：
文章图片
O(2*N) Scheme1: 一般最大的数和最小的数不会是同一个数，（除非N= 1，或者所有的数都是一样大）
==》将数组中的数分成两个部分，再从这两个部分中分别找出最大的数和最小的数目。
1 34 45 4 6 7 8 ==》（1 ，34）（5 ，4）（6 ，7）（8）【两个数为一组】这个只是概念上的分类；
在同一组中奇数和偶数位数字，将比较大的数放在偶数位上，较小的数放在奇数位上。通过N/2次比较之后，较大的数放在偶数位置上，较小的数放在奇数上 较大=》偶数位 较小=》奇数位；
上面就变成了： 1 34 4 5 6 7 8 ，
最后从奇数位置上求出min = 1，偶数位置求出max = 34 ，各需要N/2次，整个算法共需要1.5*N次。
文章图片
代码 可以看到时间复杂度已经减少了0.5N 。
scheme2: 上一种方式破坏了原来数组的结构，下面一种方法，保持数组原来的结构，时间复杂度还是1.5N;
就是将相邻的分为一组，还是一样；将同一组中较大的和max比较，较小的和min比较；
文章图片
代码 schem3: 采用分治法，有待思考；
思路： 只需要分别求出前后N/2个数的min和max ，然后去较小的min，较大的max即可。
【时间复杂度是：1.5N-2，并没有省多少】
文章图片
分治法的伪代码 拓展： 找出N个数中的第二大数，需要比较多少次？【是否可以同样使用分治法】
思路：
1、可以先找出最大的数目，然后就是在找最大的数目，这样最大最小的数目的时候都会增加一倍，一般的方法；
2、如果使用分治法，这个也时间也未必减少，最后聊个比较并不一定是最大和第二大的数进行对比的；
3、新排序，然后去第二大的数目，这个时间就为排序的时间复杂度了；最快的排序的时间复杂度也要nlogN;
文章图片
时间复杂度是N
【编程之美|编程之美 2.10找数组中的最大值和最小值】【这个种方法循环了一次】
推荐阅读
- 深入理解C#指针之美
- 编程学习|Mybatis-Plus介绍与使用
- 【周周有奖】云原生编程挑战赛“边缘容器”赛道邀你来战！
- 2022年突然涌现上百家低代码开发平台，有给不懂编程的人用的吗（）
- [GeekBand]|[GeekBand] C++面向对象高级编程-2
- 实验一|实验一 熟悉IDLE和在线编程平台
- Java|Java核心编程(14)
- spark|spark学习笔记（七）——sparkcore核心编程-RDD序列化/依赖关系/持久化/分区器/累加器/广播变量
- Java|精通Java事务编程
- 【GeekBand】C++面向对象高级编程-第八周笔记