拜托,面试别再问我最大值最小值了!!!

原创 admin  2019-01-08 17:57 

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

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

 

int find_max(int arr[n]){

    int max = -infinite;

    for(int i=0; i<n; 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<n; i++){

        if(arr[i]>max)

            max=arr[i];

        if(arr[i]<min)

            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<min2?min1:min2;

 

    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】

 

求解递归式子,得到:

f(n)=1.5n-2;

 

画外音,证明过程如下:


【式子B】不断展开能得到:

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

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

f(n/4)=2*f(n/8)+2;【式子3】

...

f(n/2^(m-1))=2*f(2^m)+2;【式子m】

 

通过这m个式子的不断代入,得到:

f(n)=(2^m)*f(n/2^m)+2^(m+1)-2;【式子C】

 

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

即【式子C】中n/2^m=2时,f(n/2^m)=f(2)=1;

此时n=2^(m+1),代入【式子C】

即f(n)=n/2 + n -2 = 1.5n-2;

 

证明过程很严谨,但我知道你没看懂。

建议再看搞定所有时间复杂度计算

 

总结,n个数:

  • 求最大值,遍历,需要n-1次计算

  • 求最大最小值,遍历,需要2n-2次计算

  • 求最大最小值,分治,时间复杂度1.5n-2

画外音:别跳出,文末有作业。

思路比结论重要,希望大家有收获。

架构师之路-分享可落地的技术文章


推荐阅读:

世界上最漂亮的排序算法

TopK与快速排序深度解析

搞定所有时间复杂度计算

拜托,面试别再问我基数排序了!

拜托,面试别再问我计数排序了!

拜托,面试别再问我桶排序了!


作业题,n个数:

(1)求最大值,n-1次计算,是最快的方法吗?

(2)求最大最小值,1.5n-2,是最快的方法吗?

本文地址:http://www.17xiuwang.com/2019/01/08/%e6%8b%9c%e6%89%98%ef%bc%8c%e9%9d%a2%e8%af%95%e5%88%ab%e5%86%8d%e9%97%ae%e6%88%91%e6%9c%80%e5%a4%a7%e5%80%bc%e6%9c%80%e5%b0%8f%e5%80%bc%e4%ba%86%ef%bc%81%ef%bc%81%ef%bc%81/
关注我们:请关注一下我们的微信公众号:扫描二维码,公众号:aiboke112
版权声明:本文为原创文章,版权归 admin 所有,欢迎分享本文,转载请保留出处!

发表评论


表情