找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 821|回复: 0
收起左侧

[资源分享] 9: Count Triangle Triple Index

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-3-2015 10:43 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

WA了好几次之后才想着尝试下是不是还要加上三角形边长不为0的条件,加上之后果然A了,真是有点坑啊,题目中定义
A triangle triple index is a triple of integers ( 0 <= P < Q < R < N ) that is defined as follows:
A[P] + A[Q] > A[R]
A[p] + A[R] > A[Q]
A[Q] + A[R] > A[P]

都没有提这个要求啊。
最简单的想法是排序之后O(n*(n-1)*(n-2))的三重循环,自己在纸上推推就会发现,其实最内层的循环是没必要每次重新赋初值的,因为对于所有满足a【i】+a[j]<a[k]的k,当j++之后肯定更加满足,从而可以把复杂度降为O(n*(n-1+n-2))。
  1. class Solution {
  2. public:
  3.         int countTriangleTripleIndex(vector<int> &A) {
  4.                 int n = A.size();
  5.                 if(n < 3) return 0;
  6.                
  7.                 sort(A.begin(), A.end());
  8.                 int tot = 0, i = 0, j, k;
  9.                 for(; i+2 < n; ++i){
  10.                         if(A【i】 == 0) continue;
  11.                         for(j = i+1, k = j+1; j+1 < n; ++j){
  12.                                 for(; k < n && A[k] < A【i】 + A[j]; ++k) ;
  13.                                 //now we have k = n || A[k] >= A【i】 + A[j]
  14.                                 //so for (a【i】,a[j]) there are k-j-1 triples that meet the requirements
  15.                                 tot += k-j-1;
  16.                         }
  17.                 }
  18.                 return tot;
  19.         }
  20. };
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表