• 周三. 6月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

力扣611 有效三角形的个数

admin

11月 28, 2021

朴素解法 三重遍历

通过三个嵌套for循环实现三角形三边所有组合的遍历,无需排序,只需要保证下标 (i < j < k) 避免重复即可;
时间复杂度 (O(n^3)), 空间复杂度 (O(n).)

排序 + 二分查找

针对上述三重遍历的方法,比较容易想到的改进方法为二分查找。我们注意到,在有序的情况下,确定第一条边a和第二条边b,第三条边c的选择范围是一个连续的区间,即(b <=c < a+b.) 值得注意的是,在值上,c可以等于b,但是在对应的下标上,必须保证$ j < k.$
根据上述思路,我们可以对所有的边长进行一次排序。然后通过双重for循环遍历前两条边,第三条边的寻找不需要进行遍历,可通过二分查找找到其可能的最大值,那么整个选择的范围也就被确定了。
时间复杂度(O(n^2logn)),空间复杂度(O(n).)

排序 + 双指针

本题最优解是通过双指针来解决。对于第三条边,如果是随机分布在第二条边之后,那么二分查找(O(logn))的复杂度已经最优,但本题仍隐含一个信息,第一条边确定时,随着第二条边的值不断变大,第三条边的上限是递增的。因此,可通过双指针,将第二重循环和第三重循环转化为总复杂度只有(O(n))的一个过程。
时间复杂度(O(n^2)),空间复杂度(O(n).)

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int res = 0;
        for(int i = 0; i < nums.size(); ++i) {
            // 遍历第一条边
            int j = i+1;              // 第二条边的下标
            int k = j;                // 第三条边没找到时的下标
            for(;j < nums.size(); ++j){
                // 遍历第二条边
                k = max(k,j);         // 上次没找到第三条边时,将第三条边初始化为当前第二条边
                while(k + 1 < nums.size()){
                    if(nums[i] + nums[j] > nums[k + 1])  ++k;
                    else break;  
                }
                res += k - j;         // (j,k] 共有 k - j 个元素
            }            
        }
        return res;
    }
};

总结

本题从暴力搜索出发,通过分析其内蕴的三边之间关系,对第三条边的遍历进行优化。遇到类似的场景可分析各重循环之间是否具有依赖性,可根据特殊的联系使用二分查找或双指针进行算法优化。

发表评论

您的电子邮箱地址不会被公开。