给出一个数组A,找出一对 (i, j)使得A[i] <= A[j] (i < j)并且j-i最大
2024-10-15 10:50:46
题目:给出一个数组A,找出一对 (i, j)使得A[i] <= A[j] (i <= j)并且j-i最大 ,若有多个这样的位置对,返回i最小的那一对。
最直接的想法就是对于每一个 i 从数组最尾端开始向前找到第一个大于等于 A[i] 的位置 j ,时间复杂度O(n^2)。
. pair<int, int> find(const vector<int> &A)
. {
. int n = A.size();
. if(n == )
. throw new invalid_argument("Array's size can't be 0!");
.
. int target_i = , target_j = ;
. int max_len = ;
. for(int i = ; i < n; ++i)
. {
. int j;
. for(j = n-; j >= i; --j)
. if(A[j] >= A[i])
. break;
. if(j-i+ > max_len)
. {
. target_i = i;
. target_j = j;
. max_len = j-i+;
. }
. }
.
. return make_pair<int, int>(target_i, target_j);
. }
我们对上述算法稍作优化。当i=0时,我们假设找到的大于A[i]的最右位置是j0,那么对于i=1时,我们根本就不需要考虑小于j0的位置,因为它们的区间长度都小于j0+1,不可能成为最优解。
. pair<int, int> find(const vector<int> &A)
. {
. int n = A.size();
. if(n == )
. throw new invalid_argument("Array's size can't be 0!");
.
. int target_i = , target_j = ;
. int max_len = ;
. for(int i = ; i < n; ++i)
. {
. int j;
. for(j = n-1; j > target_j; --j) // 此处只需检查到target_j
. if(A[j] >= A[i])
. break;
. if(j-i+ > max_len)
. {
. target_i = i;
. target_j = j;
. max_len = j-i+;
. }
. }
.
. return make_pair<int, int>(target_i, target_j);
. }
但时间复杂度仍然是O(n^2)的。我们可以继续接着上面的思路优化。其实对于位置 i 求最后一个大于等于它的位置,不需要每次都从数组尾部向前找,我们可以通过改进这个地方将时间复杂度变为O(n)。
过程是这样的,对于 i ,我们先找到 i 及其右端的最大元素的位置 j ,检查是否比当前记录的最优解更优,更新。然后考虑 j+1及其右端的最大元素位置是否大于等于A[i],若是,令 j 等于该位置,重复如上过程,若否,那么从位置i+1重新开始,但j仍然从当前位置考虑即可,原因上面已说明。这样时间复杂度就成O(n)的了。
具体请参考代码
最新文章
- C#上位机制作之串口接受数据(利用接受事件)
- SaltStack与ZeroMQ(二)
- 有用的MySQL语句
- 经典sql语句
- 网站QQ导航
- [转]iSCSI完全指南
- android开发之路11(用SharedPreferences存储数据)
- 搭建完全分布式的hadoop[转]
- ZOJ问题(坑死了)
- [置顶] 软件设计之道_读书纪要.doc
- 任意2个io直接驱动LCD1602,并且不需外加芯片(转)
- [Spark] - Spark部署安装
- iot会议纪要 20180105
- DevExpress 控件中GridControl的使用
- 线性代数导论 | Linear Algebra 课程
- Go 语言和 Scala 语言对比
- 1001. A+B Format 字符串
- 求大神帮解答calendar日期插件的问题
- nodejs安装、环境配置和测试
- Java注册帐号邮箱激活验证实现
热门文章
- android让你的TabHost滑动起来
- 仿酷狗音乐播放器开发日志二十七 用ole为窗体增加文件拖动功能(附源码)
- RPC框架motan: 通信框架netty( 1)
- 《Genesis-3D开源游戏引擎完整实例教程-2D射击游戏篇06:计分》
- 使用Cygwin通过ssh命令行来访问Windows8
- 【转】在企业内部分发 iOS 应用程序
- ext4.0绘制chart(柱状图,条形图)
- uLua学习笔记(三):Unity3D和Lua之间的相互调用
- ModelMap和ModelAndView
- PHP linux spl_autoload_register区分大小写