原题链接:http://oj.leetcode.com/problems/insert-interval/这道题跟Merge
Intervals很类似,都是关于数据结构interval的操作。事实上,Merge
Intervals是这道题的子操作,就是插入一个interval,如果出现冲突了,就进行merge。跟Merge
Intervals不一样的是,这道题不需要排序,因为插入之前已经默认这些intervals排好序了。简单一些的是这里最多只有一个连续串出现冲突,因为就插入那么一个。基本思路就是先扫描走到新的interval应该插入的位置,接下来就是插入新的interval并检查后面是否冲突,一直到新的interval的end小于下一个interval的start,然后取新interval和当前interval中end大的即可。因为要进行一次线性扫描,所以时间复杂度是O(n)。而空间上如果我们重新创建一个ArrayList返回,那么就是O(n)。有朋友可能会说为什么不in-place的进行操作,这样就不需要额外空间,但是如果使用ArrayList这个数据结构,那么删除操作是线性的,如此时间就不是O(n)的。如果这道题是用LinkedList那么是可以做到in-place的,并且时间是线性的。代码如下:public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> res = new ArrayList<Interval>();
if(intervals.size()==0)
{
res.add(newInterval);
return res;
}
int i=0;
while(i<intervals.size() && intervals.get(i).end<newInterval.start)
{
res.add(intervals.get(i));
i++;
}
if(i<intervals.size())
newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
res.add(newInterval);
while(i<intervals.size() && intervals.get(i).start<=newInterval.end)
{
newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
i++;
}
while(i<intervals.size())
{
res.add(intervals.get(i));
i++;
}
return res;
}
这道题有一个变体,就是如果插入的时候发现冲突,那就返回失败,不插入了。看起来好像比上面这道题还要简单,但是要注意的是,如此我们就不需要进行线性扫描了,而是进行二分查找,如果不冲突,则进行插入,否则直接返回失败。这样时间复杂度可以降低到O(logn)。当然这里需要用二分查找树去维护这些intervals。所以一点点变化可能可以使复杂度降低,还是应该多做思考哈。同时,这种题目还可以问一些关于OO设计的东西,比如就直接问你要实现一个intervals的类,要维护哪些变量,实现哪些功能,用什么数据结构,等等。这些你可以跟面试官讨论,然后根据他的功能要求用相应的数据结构。所以扩展性还是很强的,大家可以考虑的深入一些。
分享到:
相关推荐
前端开源库-node-interval-tree节点间隔树,实现间隔树的数据结构。
能用interval-partitioning算法设计思想解决一些贪心问题,并能用代码实现interval-partitioning 算法,以得到最优解。 一、实验目的 了解动态规划的思想,掌握0/1背包问题的基本解决方法。 二、实验要求 (1)有n...
资源分类:Python库 所属语言:Python 资源全名:interval-py-0.0.2.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
A Method for Interval-valued Intuitionistic Fuzzy Multiple Attribute Decision Making with Incomplete Weight Information,卫贵武,,With respect to multiple attribute decision making problems with ...
Using the method of maximizing deviations to multiple attribute decision making under interval-valued intuitionistic fuzzy environment,卫贵武,,With respect to multiple attribute decision making ...
python库。 资源全名:datetime-interval-0.1.tar.gz
基于Interval-based AHP的网络安全态势评估.pdf
标准Javascript»setInterval()间隔承诺»interval()安装npm install interval-promise用法使用async-await的简单示例const interval = require ( 'interval-promise' )// Run a function 10 times with 1 ...
区间值q-Rung模糊Choquet积分算子及其在群决策中的应用_Interval-valued q-Rung Orthopair Fuzzy Choquet Integral Operators and Its Application in Group Decision Making.pdf
【LeetCode】436. Find Right Interval 解题报告(Python)标签(空格分隔): LeetCode作者: 负雪明烛个人博客: h
npm install set-interval-async # If using Typescript, also run: npm install -D @types/set-interval-async 或使用Yarn: yarn add set-interval-async # If using Typescript, also run: yarn add -D @types/...
Methods of fuzzy rule extraction based on rough set theory are rarely reported in incomplete interval-valued fuzzy information systems. Thus, this paper deals with such systems.Instead of obtaining ...
使用安装git clone git://github.com/shinout/interval-tree.gitORnpm install interval-tree用法var IntervalTree = require('interval-tree');// add interval datavar itree = new IntervalTree(300); // 300 : ...
The fuzzy rough sets and generalized fuzzy rough sets have been extended by three pairs of fuzzy logical ... There are recent researches into generalized interval-valued fuzzy rough sets for inte
Interval 、 Employee 列表节点 构造函数 const node = new ListNode ( val ) 使用数组初始化 (遵循 LeetCode 主题规范): ListNode.create(arr : Array) : ListNode const head = ListNode . create ( [ 1 , 2 , ...
npm install math-interval-js 。 bower install math-interval-js 。 : composer require vluzrmos/math-interval-js 。 用法 简单的: Interval . test ( 1 , "[1,2]" ) ; // true Interval . test ( 3 , "...
npm install com.izaakschroeder.interval-tree-clock 用法: var seedStamp = require ( 'com.izaakschroeder.interval-tree-clock' ) ; var tmp = undefined , user1 = seedStamp , user2 = seedStamp ; tmp...
区间树算法描述,及其说明,使用代码形式来描述区间树问题
git clone :AKSW / temporal-interval-scoping.git mvn clean eclipse:eclipse 在Eclipse中导入现有的Maven项目import ========================= Windows安装说明 从“帮助”选项卡中的Eclipse Marketplace在...
var createIntervalTree = require ( "interval-tree-1d" ) //Create some random list of intervals var intervals = [ [ 1 , 2 ] , [ - 1 , 0 ] , [ 0.5 , 1 ] , [ - 10 , 10 ] ] //Build tree var tree = ...