Leetcode 611. 有效三角形的个数
在线提交: https://leetcode-cn.com/problems/valid-triangle-number/
给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
思路:
题中的要求数组长度不超过1000,事实上限制了算法的时间复杂度要小于O(n3)O(n3)O(n^3)。 先排序,然后采用贪心法的思想,算法复杂度可降低至O(n2)O(n2)O(n^2),如下图所示:
伪代码:
sort(nums)
for c = n-1 to 2
a, b = 0, c-1
while a<b:
if nums[a] + nums[b] > nums[c]:
count += (a-b+1)-1
b--
else
a++
已AC代码:
public class Solution
{
public int TriangleNumber(int[] nums)
{
var n = nums.Length;
if (n < 3)
return 0;
Array.Sort(nums);
// Array.Sort(array, (x, y) => -x.CompareTo(y));
var groupCount = 0;
for (int c = n - 1; c >= 2; c--)
{
int b = c - 1;
int a = 0;
while (a != b)
{
if (nums[a] + nums[b] > nums[c])
{
groupCount += b - a; // 贪心法,只要此时满足不等式,则仅有a在该区间内移动(b,c不变)时,显然也满足不等式
b--;
}
else
a++;
}
}
return groupCount;
}
}
Rank:
You are here! Your runtime beats 93.15% of csharp submissions.