唉，害得我交了七发都没过。赛后来了个题目有问题。。。。
以下贴出我的代码，不保证复杂度能达到O（nlogn），但绝对达不到O（n2）。
方法：
最大三角形：
找出最大的i满足：a[i]<a[i-1]+a[i-2] (i 属于[2,n-1]) 最大值就是三边之和（可以用俩变量去记避免溢出，例如代码中的mx、mxmx）
最小三角形：
先找到最小的i满足：a[i]<a[i-1]+a[i-2] (i 属于[2,n-1]),然后遍历去找符合条件的最小三角形。
遍历找的时候：a[j]从小找，a[k]从大找，找到满足条件且（a[j]+a[k]）最小。过程中可以有点合理剪枝即可通过。
赛时提交的代码：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回在所有合法的三角形的组成中，最大的三角形的周长减去最小的三角形的周长的值
* @param n int整型 代表题目中的n
* @param a int整型vector 代表n个数的大小
* @return int整型
*/
int solve(int n, vector<int>& a) {
// write code here
sort(a.begin(),a.end());
int mi = 2e9+7,mimx;
for(int i=2;i<n;++i)
{
if(a[i]<a[i-1]+a[i-2])
{
mimx = a[i];
for(int j =0;j<i-1;j++)
{
for(int k=i-1;k>=j+1;--k)
{
if(a[j]+a[k]>mi)
break;
if(a[i]<a[j]+a[k])
mi=min(mi,a[j]+a[k]);
if(a[j]+a[k]<=a[i])
break;
}
}
break;
}
}
int mx = 0,mxmx;
for(int i=n-1;i>=2;--i)
{
if(a[i]<a[i-1]+a[i-2])
{
mxmx = a[i];
mx = a[i-1]+a[i-2];
break;
}
}
return (int)(mx+mxmx-mi-mimx);
}
}; 若有问题，欢迎指出！ 复杂度达到O(NlogN)的可以看这个哥们的帖子：挺详细的
全部评论
(7) 回帖