内容简介:[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:
- The length of the given array won't exceed 1000.
- 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; } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
在线进制转换器
各进制数互转换器
Markdown 在线编辑器
Markdown 在线编辑器