思路:

题目的主要信息:

  • 从一个一维数组中任选4个数,组成四边形,求能组成的四边形的最大面积
  • 返回结果与正确答案的误差应小于0.00001

性质1:能够组成四边形的四条边必然满足,三边之和大于第四边
性质2:四条边已知(a,b,c,d)的四边形,最大面积(形状不确定,因为四边形有不稳定性,只能求最大面积)为
,其中
图片说明
因为我们要求的是最大面积,因此用上述公式计算面积也没错。

方法一:暴力法
具体做法:
四次遍历数组,找到所有四个数的组合,用性质1验证其是否是四边形,用性质2计算其最大面积。

class Solution {
public:
    double square(int a, int b, int c, int d){ //判断四边形是否存在且计算面积
        if(a + b + c < d || a + b + d < c || a + c + d < b || b + c + d < a) //三边之和要大于第四边 
            return 0.0;
        double sum = ((double) (a + b + c + d))/ 2;
        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长度的数组选取不重复的四个数的组合数
  • 空间复杂度:,常数个变量

方法二:排序法
具体做法:
因为要求能组成的四边形的最大面积,我们也知道确定的四边形四条边,上述公式就能算出该情况下的最大值,因此我们可以考虑直接取最大的四边形组成四边形,计算最大面积。所以我们对数组进行了排序,然后从后往前选取,只要算到了面积就跳出循环,避免了很多不必要的运算。

class Solution {
public:
    double solve(vector<int>& a) {
        sort(a.begin(), a.end()); //排序
        int n = a.size();
        double res = 0.0;
        for(int i = n - 1; i >= 0; i--)  //选取最后四个能组成四边形的组合
            for(int j = i - 1; j >= 0; j--)
                for(int k = j - 1; k >= 0; k--)
                    for(int m = k - 1; m >= 0; m--){
                        int x = a[i];
                        int b = a[j];
                        int c = a[k];
                        int d = a[m];
                        if(x + b + c > d && x + b + d > c && x + c + d > b && b + c + d > x){
                            double sum = ((double) (x + b + c + d)) / 2;
                            res = sqrt((sum - x) * (sum - b) * (sum - c) * (sum -d));
                            return res;
                        }
                    }
        return res;
    }
};

复杂度分析:

  • 时间复杂度:,最坏复杂度还是这个,但是平均复杂度有所下降,因为不用全部遍历组合数,排序复杂度远小于组合数
  • 空间复杂度:,常数个变量