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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 从更大范围中删除范围列表中的元素的有效方法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3119字，纯文字阅读大概需要5分钟。

内容图文

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

例如：

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;
    }
}

解决方法:

通过将“添加所有元素然后按范围删除”更改为“添加元素超出删除范围”,请参阅@Bohemian idea

>对rangeToBeRemoved进行排序(通过range.start)
>在范围内循环并添加未按范围覆盖的元素
>在最后一个范围结束后添加所有元素

// 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);
    }
}

对rangeToBeRemoved进行排序后,两个范围之间的关系为

>完全在范围内(例如(2,7)和(4,6))
>部分范围(例如(2,7)和(6,8))
>不在范围内(例如(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)和命中案例3进行比较,将间隙[0,1]添加到结果集中,并将borderElementIndex更改为7.
>接下来,比较(-1,7)和(4,6)并命中案例1,忽略它.
>然后,比较(-1,7)和(6,8)并命中案例2,将borderElementIndex更改为8.
>最后,将剩余差距[9,10]附加到结果集中.

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

内容总结

以上是互联网集市为您收集整理的java – 从更大范围中删除范围列表中的元素的有效方法全部内容，希望文章能够帮你解决java – 从更大范围中删除范围列表中的元素的有效方法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端