备案网站出售,小程序开发平台哪家产品较好,学校网站模板 中文,赣州建设网上一篇:算法随笔_12:最短无序子数组-CSDN博客 题目描述如下:
给定一个包含非负整数的数组 nums #xff0c;返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3 算法…上一篇:算法随笔_12:最短无序子数组-CSDN博客 题目描述如下:
给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3 算法思路:
首先我们重温一下三角形三条边的关系每两边之和大于第三边。假设三条边为e1e2e3。那么需要保证e1e2e3e1e3e2e2e3e1。
那么初步能想到的算法就是通过三层循环依次访问不同的三个数同时判断上面的三个条件是否成立。很显然时间复杂度非常高。我们考虑一下如何优化它。
由于大量的操作是比较大小既然是比较大小那么我们考虑一下如果把数组排序完之后是不是能找到更优的算法呢
我们先把数组进行升序排列。第一层循环从第一个元素开始把它做为e1第二层循环从第二个元素开始把它做为e2。e3的选择肯定在e1e2之后由于此时数组是升序排列因此有下面一系列的推理:
e3必定大于e1e2
推出e1e3e2e2e3e1肯定成立
推出我们只需要判断e1e2e3这个条件。
此时问题已经简化。但是e3也需要第三层循环吗那样做的话和上面的算法就一样了。此时我们从另一个角度考虑一下这个问题。判断e1e2e3是不是就相当于从e1e2后面的元素里寻找一个特定的值e3。从某组有序的数列中查找一个特定的值我们立刻就能想到可以使用二分查找法。
使用二分查找法的基本思想就是:
1. 我们设e1e2后面的那个数组区间为seg。设e3的最大值为e3_max。
2. 计算得出seg的中间元素e_mid判断e1e2是否大于e_mid。如果小于说明e3_max肯定不在seg区间的右半边我们把seg重新赋值为seg区间的左半边。如果大于说明e3_max有可能在seg区间的右半边我们把seg重新赋值为seg区间的右半边。然后重复步骤2直至找到e3_max。
那么e3_max的左侧所有元素均可做为e3的候选都满足e1e2e3。此时e1e2e3都已经找出。算法的时间复杂度为。
接下来我们继续优化上面的算法。假设现在我们找到了第一组e1e2e3_max当访问下一个e2时下一个e3_max一定出现在当前e3_max的右侧。即当e2递增时e3_max也在递增。
和上面的算法类似优化后的算法如下:
1. 我们先设个变量e3_max_ind表示e3_max的下标。
2. 我们同样使用两层循环分别迭代e1e2将e3_max_ind设置为e2的下一个元素并不断的向右寻找直到找到最大的e3且满足e1e2e3即e3_max。
3. 在第二层循环继续访问下一个e2此时只需要从当前的e3_max_ind处开始寻找下一个e3_max。
在两层循环完成之后我们就找到了所有的e1e2e3。此算法的时间复杂度为。
实现上述算法时要注意一些边界问题比如: 找不到e3的情况。
