java - 从更大范围的范围列表中删除元素的有效方法

Question

我正在寻找一种从更大范围中删除范围列表的有效方法。范围列表将包含更大的范围

例如:

Bigger range: (0,10) 
List of Ranges:  [(2,7),(4,6),(6,8)]
expected result: {0,1,9,10}

我在下面有一个实现，但它是 O(n2) 并且占用大小为 O(n) 的额外空间；

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/***
* input -> (0,10) and {(2,7),(4,6),{6,8}}
 * output -> {0,1,9,10}
 ***/
public class RemoveRanges {

    public static class Range {
        int start;
        int end;

        public Range(int x, int y){
            this.start = x;
            this.end = y;

        }
    }

    public static void main(String[] args) {

        Range outer = new Range(0,10);
        Range r1 = new Range(2,7);
        Range r2 = new Range(4,6);
        Range r3 = new Range(6,8);
        List<Range> rangesToBeRemoved = new ArrayList<>();
        rangesToBeRemoved.add(r1);
        rangesToBeRemoved.add(r2);
        rangesToBeRemoved.add(r3);

        System.out.println(removeRanges(outer, rangesToBeRemoved));

    }

    public static Set<Integer> removeRanges(Range outer, List<Range> rangesToBeRemoved ) {

        Set<Integer> outerElements = new HashSet<>();

        for (int i = outer.start; i<=outer.end;i++ ){
            outerElements.add(i);
        }

        for (Range range : rangesToBeRemoved) {
            for (int j = range.start; j<=range.end; j++) {
                outerElements.remove(j);
            }
        }
        return outerElements;
    }
}

Answer 1

通过将方法从“添加所有元素然后按范围删除”更改为“添加超出删除范围的元素”来引用@Bohemian 的想法

1. 对 rangesToBeRemoved 进行排序(按 range.start)
2. 遍历范围并添加未被范围覆盖的元素

3. 添加最后一个范围结束后的所有元素

   // assume rangesToBeRemoved has been sorted
   public static Set<Integer> addElementbyRemovedRanges(Range outer, List<Range> rangesToBeRemoved ) {
   
       Set<Integer> outerElements = new HashSet<Integer>();
   
       // this variable record the last element that has handled and act like a borderline
       int borderElementIndex = outer.start-1;
       for (Range range : rangesToBeRemoved) {
           if (range.end <= borderElementIndex ) {
               // omit this range as it has been cover by previous range(s)
               continue;
           }
   
           // add range if there is gap between range
           if (range.start > borderElementIndex ) {
               addElements(outerElements, borderElementIndex + 1, range.start - 1);
           }
   
           // update borderline
           borderElementIndex = range.end;
       }
       // Add all element after the last range's end
       addElements(outerElements, borderElementIndex + 1, outer.end);
   
       return outerElements;
   }
   
   public static void addElements(Set<Integer> outerElements, int start, int end) {
       if (start > end) {
           return;
       }
       for (int i=start; i<=end; i++){
           outerElements.add(i);
       }
   }
   

---

对rangesToBeRemoved排序后，两个range之间的关系为

1. 完全在范围内(例如 (2,7) 和 (4,6))
2. 部分在范围内(例如 (2,7) 和 (6,8))
3. 不在范围内(例如 (2,3) 和 (6,8) || (2,3) 和 (4,8))

对于情况 1，忽略第二个范围。对于情况 2，将边界线更新为第二个范围的末尾。对于情况 3，将间隙添加到元素列表并将边界线更新到第二个范围的末尾。

上面的代码试图比较虚拟范围 (outer.start-1, borderElementIndex) 和 rangesToBeRemoved 中的所有范围(已排序)

重复使用您的示例:{(2,7),(4,6),(6,8)}。

• 首先比较(-1,-1)和(2,7)，命中case 3，将gap[0,1]加入结果集中，borderElementIndex为7。
• 接下来，将 (-1,7) 与 (4,6) 进行比较并命中案例 1，忽略它。
• 然后，比较 (-1,7) 和 (6,8) 并命中情况 2，将 borderElementIndex 更改为 8。
• 最后，将剩余的间隙 [9,10] 添加到结果集中。

---

为了进一步减少空间使用，您可以在@Danny_ds 解决方案中使用相同的想法状态来存储元素的范围而不是单个元素。