题解 | #最大四边形面积#

最大四边形面积

http://www.nowcoder.com/practice/0eaf4653f1d243d4a46b3d5d60a7362e

题目:最大四边形面积
描述:给定大小为n的整数集合A,代表n根木棍的长度。从A中任选4根木棍组成一个四边形,求其面积最大为多少。数据保证有解。
程序返回结果与正确答案的误差应小于0.00001
示例1:输入:[1,2,3,4,5],返回值:10.95445

解法一:
  思路分析+实例分析:该题目的意思是求解存在的最大四边形的面积,因为题目中给定大小为n的整数集合代表木棍的长度,从整数集合A中任意选取4根木棍组成四边形,在计算这道数学题的过程中,我们首先应该明白什么叫四边形,四边形的判定条件是什么,任意四边形的面积是怎么计算,所以笔者去查阅了相关资料做出以下解释。
  众所周知,对于指定的三条边a,b,c,它首尾相接可以构成一个三角形的条件是:

a < b + c,b < a + c,c < a + b
  这就是我们学的三角形两边之和大于第三边的结论,在四边形中,我们仍然可以引用上面的几何公理,由此得到一个必要条件就是:
a < b + c + d,b < a + c + d,c < a + b + d,d < a + b + d
  具体的判定过程就不进行一一分析了,我们直接进行使用。下面进行四边形面积的分析,因为这道题中给定了一个条件就是四边形的边长都已经给定了,所以我们采用的公式如下图所示:

图片说明
  通过上述分析,我们已经具备了写程序的所有条件,下面展示程序。
C++核心程序为:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return double浮点型
     */
    double F(double a,double b,double c,double d){
        if(a + b + c < d||a + b + d < c || a + c + d < b || b + c + d < a)
            //不满足形成四边形的条件
            return 0.0;
        double z = (a + b + c + d) / 2;//z值得计算条件
        return sqrt((z-a)*(z-b)*(z-c)*(z-d));
    }

    double solve(vector<int>& a) {
        // write code here
         int len = a.size();//a数组得长度
         double  res = 0;//最终结果
        for(int i = 0;i < len - 3;i++)//四层嵌套循环
            for(int j = i + 1;j < len - 2;j++)
                for(int k = j + 1;k < len - 1;k++)
                    for(int l = k + 1;l < len;l++)
                    {
                        res = max(res,F(a[i],a[j],a[k],a[l]));
                    }
        return res;
    }
};

  在该算法中,因为有四层嵌套的for循环,所以其循环次数为图片说明 ,但是在其中有重复的数组不需要进行计算,即当i等于0的值的时候,j不等于0的值等等,就相当于从n个数字中寻找不重复的四个数字,所以其时间复杂度为图片说明 ,因为不需要任何额外的存储空间,所以其空间复杂度为

解法二:
  思路分析:我们对解法一进行优化,因为我们知道,既然选择最大面积,所以我们可以初始化的时候,对数组进行排序,对数组中的元素进行倒排序(从大到小),可以节省很多时间,sort(a.rbegin(), a.rend()),然后初始化一个指针i,从3开始判断,因为前面至少还需要三个数,才能组成四条边的四边形,同样我们使用上述公式,在满足四边形的基本条件下,求解z和面积。
C++核心代码为:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return double浮点型
     */
    double solve(vector<int>& a) {
        // write code here
        sort(a.rbegin(), a.rend());//首先进行排序,倒序
        for (int i = 3; i < a.size(); ++i) {//因为必须有4条边,所以i的值为3
            if (a[i - 3] < a[i - 2] + a[i - 1] + a[i]) {//判断满足的条件
                double z = (a[i - 3] + a[i - 2] + a[i - 1] + a[i]) / 2.0;
                //计算得到z的大小,通过公式进行计算
                return sqrt((z - a[i - 3]) * (z - a[i - 2]) * (z - a[i - 1]) * (z - a[i]));
            }
        }
        return 0;
    }
};

  在上述算法中,只需要循环一次,便可以计算出最大值,因为采用了sort排序,sort排序的时间复杂度为,所以时间复杂度为,不需要占用额外的内存空间,所以其空间复杂度为

算法自然分析 文章被收录于专栏

在解决问题的同时,不断与人交流学习,通过牛客各式各样的题目,学习分享。

全部评论

相关推荐

点赞 收藏 评论
分享
正在热议
# 牛客帮帮团来啦!有问必答 #
1151501次浏览 17149人参与
# 通信和硬件还有转码的必要吗 #
11202次浏览 101人参与
# 不去互联网可以去金融科技 #
20362次浏览 255人参与
# 和牛牛一起刷题打卡 #
18967次浏览 1635人参与
# 实习与准备秋招该如何平衡 #
203374次浏览 3625人参与
# 大厂无回复,继续等待还是奔赴小厂 #
4972次浏览 30人参与
# OPPO开奖 #
19200次浏览 267人参与
# 通信硬件薪资爆料 #
265899次浏览 2484人参与
# 国企是理工四大天坑的最好选择吗 #
2220次浏览 34人参与
# 互联网公司评价 #
97682次浏览 1280人参与
# 简历无回复,你会继续海投还是优化再投? #
25035次浏览 354人参与
# 0offer是寒冬太冷还是我太菜 #
454860次浏览 5124人参与
# 国企和大厂硬件兄弟怎么选? #
53901次浏览 1012人参与
# 参加过提前批的机械人,你们还参加秋招么 #
14644次浏览 349人参与
# 硬件人的简历怎么写 #
82285次浏览 852人参与
# 面试被问第一学历差时该怎么回答 #
19397次浏览 213人参与
# 你见过最离谱的招聘要求是什么? #
28086次浏览 248人参与
# 学历对求职的影响 #
161234次浏览 1804人参与
# 你收到了团子的OC了吗 #
538706次浏览 6386人参与
# 你已经投递多少份简历了 #
344213次浏览 4963人参与
# 实习生应该准时下班吗 #
96976次浏览 722人参与
# 听劝,我这个简历该怎么改? #
63523次浏览 622人参与
牛客网
牛客企业服务