删除一个ArrayList相交值 [英] delete intersecting values in an arraylist

问题描述

我有一类这样的

 公共类Func键{
    字符串ID;
    长的startTime;
    长endTime的;
}
 

和在我的这些类对象的列表的方法之一

 名单，其中，Func键＆GT; funList =新的ArrayList＆LT; Func键＆GT;（）;
 

最新最好的办法从这个funList的startTime和endTime的相交在同一列表中的其他对象中删除的对象。

我能想到的一种方法是采取每个对象列表中的，并与其它的目的进行比较，并把该ID在其它数据结构中，如果它相交。之后的每一个对象进行比较等，经过数据结构，其中ID是保存和从列表中删除它们。

解决方案

1. 在排序的startTime下降，endTime的acsending。
2. 扫描阵列由左到右夹持元件与目前最大右端/
   1. 如果新项目的左端小于当前的最大权则既标记为删除。
   2. 右键如果需要更新的最大值。

复杂度：为O（n LN N）

修改例如

1. （1，3）（2,4）（5,6）
2. curmax = -inf
3. curmax = 3
4. 2'; 3 - 标记的第一和第二的坏。 curmax = 4
5. 5> 4 - 什么都不做。 curmax = 6。
6. （5,6） - 是唯一的好段

I have a class like this

    public class Func {
    String id;
    long startTime;
    long endTime;
}

and in one of the methods I have list of these class objects

List<Func> funList = new ArrayList<Func>();

Whats the best way to remove the objects from this funList whose startTime and endTime intersect with another object in the same list.

One way I can think of is to take each object in the list and compare with other objects and put the id in an other data structure if it intersects. After every object is compared against other, go through the datastructure where ID's are save and remove them from the List.

解决方案

1. Sort by startTime descending, endTime acsending.
2. Scan array from left to right holding element with currently max right end/
   1. If new item's left end is less than current max right then mark both for deletion.
   2. Update maximum right if needed.

Complexity: O(n ln n)

EDIT example:

1. (1, 3) (2, 4) (5, 6)
2. curmax = -inf
3. curmax = 3
4. 2 < 3 - mark first and second as "bad". curmax = 4
5. 5 > 4 - do nothing. curmax = 6.
6. (5,6) - is the only good segment.

这篇关于删除一个ArrayList相交值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！