c 取数组最大值算法_拜托，面试别再问我最大值最小值了！！！

╰半夏微凉° 2022-10-25 14:08 165阅读 0赞

**如何从n个数里找到最大值？**

很容易想到，用一个循环就能搞定。

> *int find\_max(int arr\[n\])\{* 
> 
> *    int max = -infinite;*
> 
> *    for(int i=0; i*
> 
> *        if(arr\[i\]>max)*
> 
> *            max=arr\[i\];*
> 
> *    return max;*
> 
> *\}*

这里，需要执行n-1次比较。

**如何从n个数里找到最大值与最小值？**

很容易想到，用一个循环找到最大值和最小值，就能搞定。

> *(int, int) find\_max\_min(int arr\[n\])\{* 
> 
> *    int max = -infinite;*
> 
> *    int min = infinite;*
> 
> *    for(int i=0; i*
> 
> *        if(arr\[i\]>max)*
> 
> *            max=arr\[i\];*
> 
> *        if(arr\[i\]*
> 
> *            min=arr\[i\];*
> 
> *    \}*
> 
> *    return (max, min);*
> 
> *\}*

这里，需要执行2\*(n-1)=2n-2次比较。

**还有没有更快的方法呢？**

分治法或许可以派上用场，分治法的思路是：

(1)把大规模拆分成小规模；

(2)小规模分别求解；

(3)小规模求解之后，再综合求解大规模；

看能不能往这个例子里套用：

(1)将arr\[0,n\]分为arr\[0,n/2\]和arr\[n/2,n\]；

(2)每个子数组分别求解最大值和最小值；

(3)两个子数组的最大值里再取最大值，两个子数组的最小值里再取最小值，就是最终解；

伪代码大概是这样：

> *(int, int) find\_max\_min(int arr\[0,n\])\{* 
> 
> *   * *// 递归左半区*
> 
> *    (max1, min1) = find\_max\_min(arr\[0, n/2\]);*
> 
> *   * *// 递归右半区*
> 
> *    (max2, min2) = find\_max\_min(arr\[n/2, n\]);*
> 
> *   * *// 再计算两次*
> 
> *    max = max1>max2?max1:max2;*
> 
> *    min = min1*
> 
> *    return (max, min);*
> 
> *\}*

*画外音，实际的递归代码要注意：*

*(1)入参不是0和n，而是数组的下限和上限；*

*(2)递归要收敛，当数组的上下限相差1时，只比较一次，直接返回max和min，而不用再次递归；*

**分治法之后，时间复杂度是多少呢？**

如果你是“架构师之路”的老读者，《搞定所有时间复杂度计算》一文，能够轻松求解分治法的时间复杂度分析：

*  当只有2个元素时，只需要1次计算就能知道最大，最小值
 *  当有n个元素时，

(1)递归左半区；

(2)递归右半区；

(3)再进行两次计算；

f(2)=1;【式子A】

f(n)=2\*f(n/2)+2;【式子B】

求解递归式子，得到：