找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 722|回复: 2
收起左侧

[资源分享] 9 Count Triangle Triple Index

[复制链接]

48

主题

5

精华

383

积分

高级会员

Rank: 3Rank: 3

积分
383

最佳新人

发表于 6-1-2015 04:52 AM | 显示全部楼层 |阅读模式

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

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

x
O(n^2), since in the while loop, k always increasing instead of reset when a new j comes...
  1.     // http://www.geeksforgeeks.org/find-number-of-triangles-possible/
  2.     static int countTriangleTripleIndex(int [] A) {
  3.         Arrays.sort(A);
  4.         int cnt = 0;
  5.         for(int i=0; i<=A.length-3; i++) {
  6.             int k = i + 2;
  7.             for(int j=i+1; j<A.length; j++) {
  8.                 while(k<A.length && A【i】+A[j]>A[k])
  9.                     k++;

  10.                 cnt += Math.max(0, k-j-1);
  11.             }
  12.         }

  13.         return cnt;
  14.     }
复制代码


发表于 6-1-2015 02:07 PM | 显示全部楼层
Thanks for your sharing~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

4

主题

0

精华

54

积分

资深会员

Rank: 2

积分
54
发表于 2-26-2016 06:58 AM | 显示全部楼层
需要加上一个对K值得判断,保证K值一直在最右边才可以通过。
  1. class Solution {
  2.         int countTriangleTripleIndex(int [] A) {
  3.                 Arrays.sort(A);
  4.                 int n = A.length;
  5.                 int sum = 0;
  6.                 for (int i = 0; i < n-2; i++) {
  7.                         int k = i + 2;
  8.                         for(int j = i + 1; j < n - 1; j++) {
  9.                                 if ( k <= j )
  10.                                         k = j + 1;
  11.                                 while((k < n) && (A【i】 + A[j] > A[k]))
  12.                                         k++;
  13.                                 sum += k - j - 1;
  14.                         }
  15.                 }
  16.                 return sum;
  17.         }
  18. }
复制代码

回复 支持 反对

使用道具 举报

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

本版积分规则

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