双指针(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 <= 10000 <= 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掉一些时间复杂度过高的方法,为大家节约时间,当然如果你实在没招,暴力枚举你可以尝试一下,特别是在蓝桥杯中!!!
最后我每天都会更新一道经典算法题(正常情况下),感兴趣的宝子们可以关注我!!!
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓
所有算法题我都会放在我的专栏[经典算法练习],大家也可以关注下,我们明天见!!!