三角形计数

最近,在做lintcode 上的题目,有一些题还是很有意思的。这个属于中等难度的三角形计数。
题目:

给定一个整数数组,在该数组中,寻找三个数,分别代表三角形三条边的长度,问,可以寻找到多少组这样的三个数来组成三角形?

首先,我们能想到的解法肯定是,将所有数组合,然后判断。
代码如下:

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int S[]) {
        int result = 0;
        for (int i = 0; i < S.length - 2; i++) {
            for (int j = i + 1; j < S.length - 1; j++) {
                for (int k = j + 1; k < S.length; k++) {
                    if (trigangleJudge(S[i], S[j], S[k])) {
                        result++;
                    }
                }
            }
        }
        return result;
    }
    public  boolean trigangleJudge(int a, int b, int c) {
        if (a + b > c && a + c > b && b + c > a) {
            return true;
        } else {
            return false;
        }
    }
   
}

但是永远没有最好的解决办法,所以我在网上一直想找一个更好的方法,此时看到一篇博客。其思想是,我们先找两条边,然后利用二分查找第三条边。这位前辈是用Python写的,这里我用java。很佩服他的思路。放到这里供大家借鉴思考
代码如下:

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int S[]) {
     int result = 0;
        Arrays.sort(S);
        for (int i = 0; i < S.length; i++) {
            for (int j = i + 1; j < S.length; j++) {
                int l = i + 1;
                int r = j;
                int target = S[j] - S[i];
                while (l < r) {
                    int mid = (l + r) / 2;
                    if (S[mid] > target) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }

                }
                result += (j - l);
            }
        }
        return result;
    }

   
}

两份解决方案的测试结果如下:

第一种.png
第二种.png
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 描述 给定一个整数数组,在该数组中,寻找三个数,分别代表三角形三条边的长度,问,可以寻找到多少组这样的三个数来组成...
    6默默Welsh阅读 251评论 0 0
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,768评论 0 33
  • 1 前言 一直想沿着图像处理这条线建立一套完整的理论知识体系,同时积累实际应用经验。因此有了从使用AVFounda...
    RichardJieChen阅读 5,771评论 5 12
  • 有少年妾意郎情花前月下 有月下书生款款提笔以梦为马 有竹马夙夜匪懈绣户人家 有人家高堂斜卧与我区区足下 有足下绮罗...
    驭魂师阅读 381评论 0 1
  • 01 文清 认识文清前,我经常一个人,很孤独,上学课余也没有什么朋友。文清,是我第一个真正意义上的朋友,我真的很喜...
    我来自稀里糊涂星球阅读 305评论 0 1