双指针(5)_单调性_有效三角形的个数

2024-09-07 22:28

本文主要是介绍双指针(5)_单调性_有效三角形的个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

双指针(5)_单调性_有效三角形的个数

收录于专栏【经典算法练习
本专栏旨在分享学习C++的一点学习笔记,欢迎大家在评论区交流讨论💌

目录

1. 题目链接:

2.题目描述 :

3.解法 :

    解法一(暴力枚举) :

    算法思路 :

    代码展示 :

暴力枚举优化:

    结果分析 :

    解法二(排序 + 双指针) :

    算法思路 :

    代码展示 :

    结果分析 :

    4.总结 :


1. 题目链接:

--------有效三角形的个数

2.题目描述 :

给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

3.解法 :

    解法一(暴力枚举) :

    算法思路 :

利用三层for循环遍历整个数组

注意:

1. 这道题不需要去重处理,比如示例一中的2,3,4出现了两次,但其中的2分别是第一个和第二个.

2. 这道题的数据范围:nums.lengh <= 1000,我们三层for循环时间复杂度就为O(n^3),我们还需要进行判断,整体下来还是O(N^3),数据量超过10^9,可能会超时!!!

伪代码展示:

for (int i = 0; i < n; i++)
{for (int j = i + 1; j < n; j++){for (int k = j + 1; k < n; k++){check(i, j, k);}}
}

    代码展示 :

class Solution {
public:bool check(int a, int b, int c){if((a + c > b) && (a + b > c) && (b + c > a)) return true;else return false;}int triangleNumber(vector<int>& nums) {int sum = 0, n = nums.size();for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++)for(int k = j + 1; k < n; k++)if(check(nums[i], nums[j], nums[k])) sum++;return sum;}
};

 

很显然,在算法题中想要用暴力做出来是基本不可能的,更何况这道题还是中等的难度,通过率仅仅50%,这里我使用暴力只通过了231个例子,这里说一下暴力算法主要是为了蓝桥杯(暴力杯),当我们没有思路时,可以选择暴力方法通过一部分例子,也可以帮助我们分析题目.

优化暴力算法: 

我们可以发现,我们使用三层循环时间复杂度为O(N^3),数据量为10^9,按道理应该勉强能过,但实际上,我们三层循环里还要进行一次判断,所以时间复杂度可以细化为O(3N^3),那我们能不能把判断这个环节进行优化呢?答案是可以的!

优化判断函数check:

假设我们的数组是有序的,拿我们判断三个有序的数是否能构成三角形是不是只需要判断a + b > c就可以了,因为a <= b, b <= c,那我们的a + c一定是大于b,同理b + c 也一定大于a.

在这个思路上,我们就可以首先对数组进行排序,排序的时间为O(Nlog(N))(sort底层用的是快排),这样三层循环内的判断只需要进行一次,总体时间复杂度为O(N^3 + Nlog(N)) 是远小于 O(3N^3)的,我们看一下优化后的暴力算法能不能蒙混过关!

暴力枚举优化:

class Solution {
public:bool check(int a, int b, int c){if(a + b > c) return true;else return false;}int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int sum = 0, n = nums.size();for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++)for(int k = j + 1; k < n; k++)if(check(nums[i], nums[j], nums[k])) sum++;return sum;}
};

 

???????????????????????????????????????????????????????????????

不是,我就试一试,你就让我过了?

这道题真是中等难度吗?

说实话,我一开始只是认为会多通过几个例子,没想到它直接通过了!!!

那现在看来暴力算法还是可以作为先锋的,万一过了呢?

    结果分析 :

因为这道题数据给的比较低,数组中的数小于1000,这就给了暴力算法窜了空子,稍微优化一下,我们的暴力算法就可以通过.

但是,假如这道题数组中的数小于10000时,暴力算法无论怎么优化都不行,因为它的时间复杂度本质就是O(N^3),当数据量为10000时,我们就得考虑时间复杂度为O(N^2)或者O(Nlog(N))的算法了

    解法二(排序 + 双指针) :

    算法思路 :

先将数组排序.

根据[解法一]中的优化思想,我们可以固定一个[最长边],然后在比这条小的有序数组中找出一个二元组,使这个二元组之和大于这个最长边.由于数组是有序的,我们可以利用[对撞指针]来优化.

设最长枚举i位置,区间[left, right]是i位置的左边的区间(也就是比它小的区间):

        如果nums[left] + nums[right] > nums[i]:

                说明[left, right-1] 区间上的所有元素均可以与nums[right]构成比nums[i]大的二元组

                满足条件的有right - left

                此时right位置的元素的所有情况相当于全部考虑完毕,right--,进入下一轮判断

        如果nums[left] + nums[right] <= nums[i]:

                说明left位置的元素是不可能与[left + 1, right]位置上的元素构成满足条件的二元组

                left位置的元素可以舍去,left++进入下轮循环

思路图解:

 

    代码展示 :

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int sum = 0, n = nums.size() - 1;while(n >= 2){int left = 0, right = n - 1;while(left < right){if(nums[left] + nums[right] > nums[n]) sum += right - left, right--;else left++;}n--;}return sum;}
};

 

    结果分析 :

顺利通过!!!

时间复杂度分析:

外层n进行了一层循环,内层left和right共同完成了对数组的遍历

整体的时间复杂度为O(N^2),比前面的暴力算法还是快了不少!!!

    4.总结 :

大家做算题题时,一定要优先查看题目的数据范围,这样能提前Pass掉一些时间复杂度过高的方法,为大家节约时间,当然如果你实在没招,暴力枚举你可以尝试一下,特别是在蓝桥杯中!!!

最后我每天都会更新一道经典算法题(正常情况下),感兴趣的宝子们可以关注我!!!

欢迎 点赞👍 收藏✨ 留言✉ 加关注💓

所有算法题我都会放在我的专栏[经典算法练习],大家也可以关注下,我们明天见!!!

这篇关于双指针(5)_单调性_有效三角形的个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146338

相关文章

一文教你PyCharm如何有效地添加源与库

《一文教你PyCharm如何有效地添加源与库》在使用PyCharm进行Python开发的时候,很多时候我们需要添加库或者设置源,下面我们就来和大家详细介绍一下如何在PyCharm中添加源和库吧... 在使用PyCharm进行python开发的时候,很多时候我们需要添加库或者设置源。这些操作可以帮助我们更方便

OpenManus本地部署实战亲测有效完全免费(最新推荐)

《OpenManus本地部署实战亲测有效完全免费(最新推荐)》文章介绍了如何在本地部署OpenManus大语言模型,包括环境搭建、LLM编程接口配置和测试步骤,本文给大家讲解的非常详细,感兴趣的朋友一... 目录1.概况2.环境搭建2.1安装miniconda或者anaconda2.2 LLM编程接口配置2

Linux虚拟机不显示IP地址的解决方法(亲测有效)

《Linux虚拟机不显示IP地址的解决方法(亲测有效)》本文主要介绍了通过VMware新装的Linux系统没有IP地址的解决方法,主要步骤包括:关闭虚拟机、打开VM虚拟网络编辑器、还原VMnet8或修... 目录前言步骤0.问题情况1.关闭虚拟机2.China编程打开VM虚拟网络编辑器3.1 方法一:点击还原VM

解决java.lang.NullPointerException问题(空指针异常)

《解决java.lang.NullPointerException问题(空指针异常)》本文详细介绍了Java中的NullPointerException异常及其常见原因,包括对象引用为null、数组元... 目录Java.lang.NullPointerException(空指针异常)NullPointer

查询SQL Server数据库服务器IP地址的多种有效方法

《查询SQLServer数据库服务器IP地址的多种有效方法》作为数据库管理员或开发人员,了解如何查询SQLServer数据库服务器的IP地址是一项重要技能,本文将介绍几种简单而有效的方法,帮助你轻松... 目录使用T-SQL查询方法1:使用系统函数方法2:使用系统视图使用SQL Server Configu

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

【WebGPU Unleashed】1.1 绘制三角形

一部2024新的WebGPU教程,作者Shi Yan。内容很好,翻译过来与大家共享,内容上会有改动,加上自己的理解。更多精彩内容尽在 dt.sim3d.cn ,关注公众号【sky的数孪技术】,技术交流、源码下载请添加微信号:digital_twin123 在 3D 渲染领域,三角形是最基本的绘制元素。在这里,我们将学习如何绘制单个三角形。接下来我们将制作一个简单的着色器来定义三角形内的像素

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ