[LeetCode]Valid Triangle Number

栏目: 编程工具 · 发布时间: 7年前

内容简介:[LeetCode]Valid Triangle Number

题目描述:

LeetCode 611. Valid Triangle Number

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

  1. The length of the given array won't exceed 1000.
  2. The integers in the given array are in the range of [0, 1000].

题目大意:

给定非负整数数组,求其中可以组成三角形的三元组的个数。

解题思路:

解法I 排序(Sort) + 二分查找(Binary Search)

时间复杂度O( n^2 * log(n) )

对输入数组nums排序

枚举长度较小的两条边,利用二分查找符合条件的最大边的下标。

Java代码:

public class Solution {
    
    public int binarySearch(int[] nums, int start, int target) {
        int left = start, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
    
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int size = nums.length;
        int ans = 0;
        for (int i = 0; i < size - 2; i++) {
            for (int j = i + 1; j < size - 1; j++) {
                int k = binarySearch(nums, j + 1, nums[i] + nums[j]);
                ans += k - j - 1;
            }
        }
        return ans;
    }

}

解法II 排序(Sort) + 双指针(Two Pointers)

时间复杂度O(n^2)

对输入数组nums排序

枚举长度最小的边,利用双指针寻找符合条件的长度较大的两条边。

感谢网友 @翼灵贰駟 补充(http://weibo.com/shohku11wrj)

Java代码:

public class Solution {
	
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int size = nums.length;
        int ans = 0;
        for (int i = 0; i < size - 2; i++) {
        	if (nums[i] == 0) continue;
        	int k = i + 2;
        	for (int j = i + 1; j < size - 1; j++) {
        		while (k < size && nums[k] < nums[i] + nums[j]) k++;
        		ans += k - j - 1;
        	}
        }
        return ans;
    }

}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

网站项目管理

网站项目管理

[美] 阿什利·弗里德莱因 / 李保庆、杨磊、王增东 / 电子工业出版社 / 2002-11 / 32.00元

这本书全方位地介绍了如何建立和最终交付一个具有很高商业价值的成功网站,讲解从项目管理的角度入手,撇开烦琐的技术细节,更加关注Web项目实施中诸如成本、进度、工作范围等问题,涉及了一个商业网站在实施过程中可能遇到的所有管理细节。书内附国际一流网站开发专家的深邃见解;涵盖了网络项目管理的关键原则及案例研究;通过友情链接,还为读者提供了模板、论坛、术语表、相关链接以及有关因特网知识的测验题。一起来看看 《网站项目管理》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器