题解 | #最大四边形面积#
最大四边形面积
http://www.nowcoder.com/practice/0eaf4653f1d243d4a46b3d5d60a7362e
最大四边形面积
问题描述：给定大小为n的整数集合A，代表n根木棍的长度。从A中任选4根木棍组成一个四边形，求其面积最大为多少。数据保证有解。程序返回结果与正确答案的误差应小于0.00001
示例
输入：[1,2,3,4,5]
返回值：10.95445
方法一
思路分析
本题可以直接使用暴力搜索的办法，即设置四层循环，每次找到四条边的长度，先判断是否可以构成四边形，而后计算四边形的面积。判断构成四边形的条件：三边之和大于第四边
四边形的最大面积：
图解
四层循环遍历找到符合条件的最优解
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @return double浮点型
*/
bool judge(int a,int b,int c,int d)
{
int total = a+b+c+d;
int maxn = max(a,b);
maxn = max(maxn,c);
maxn = max(maxn,d);
if(total > 2*maxn) //判断能否构成四边形
return true;
return false;
}
double square(int a, int b, int c, int d){
if(!judge(a,b,c,d))
return 0.0;
double sum = ((double) (a + b + c + d))/ 2.0;
return sqrt((sum - a) * (sum - b) * (sum - c) * (sum -d)); //计算面积
}
double solve(vector<int>& a) {
int n = a.size();
double res = 0.0;
for(int i = 0; i < n; i++) //四次遍历找到四条边
for(int j = i + 1; j < n; j++)
for(int k = j + 1; k < n; k++)
for(int m = k + 1; m < n; m++)
res = max(res, square(a[i], a[j], a[k], a[m]));
return res;
}
}; 复杂度分析
- 时间复杂度：设置了四层嵌套循环，循环次数为
，即从$n$个数中找到4个元素，因此时间复杂度最大为
- 空间复杂度：空间复杂度为$O(1)$
方法二
思路分析
方法一中没有对给定的数组元素排序，要想得到最大的四边形的，首先对数组元素降序排序，然后循环遍历找到第一个可以构成四边形的四个边，然后输出其最大面积。图解
对数组元素降序排序后，从第四个元素出发循环遍历，与之前三个元素构成四边形的四条边，如果可以构成那么计算其面积，这样挑出的边是最长的，那么面积是最大的，即可输出结果
C++核心代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @return double浮点型
*/
static bool cmp(int a,int b)
{
return a>b;
}
bool judge(int a,int b,int c,int d)
{
int total = a+b+c+d;
int maxn = max(a,b);
maxn = max(maxn,c);
maxn = max(maxn,d);
if(total > 2*maxn) //判断能否构成四边形
return true;
return false;
}
double square(int a, int b, int c, int d)
{
double sum = ((double) (a + b + c + d))/ 2.0;
return sqrt((sum - a) * (sum - b) * (sum - c) * (sum -d)); //计算面积
}
double solve(vector<int>& a) {
// write code here
sort(a.begin(), a.end(),cmp);//首先从大到小排序
int n=a.size();
for (int i = 3; i < n; ++i)
{
int j=a[i-3];
int k=a[i-2];
int l=a[i-1];
int m=a[i];
if (judge(j,k,l,m))
{
return square(j,k,l,m);
}
}
return 0;
}
}; 复杂度分析
- 时间复杂度：与方法一相比，该方法的时间复杂度在于将数组元素进行排序时间复杂度为$O(n\log n)$，而后找到第一组边长最大且能构成四边形的数组元素，共需要循环遍历$n$次，因此时间复杂度为$O(n\log n)$
- 空间复杂度：空间复杂度为$O(1)$
查看23道真题和解析