logo标签列表

从一个较大的范围中高效地删除一组范围列表中的元素

javaalgorithmdata-structures
4

我希望找到一种高效的方法，从一个更大的范围中删除一组范围。

这个范围组将包含在更大的范围内。

例如：

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;
    }
}
2
对范围进行排序，然后使用外部范围的循环跳过范围并输出。 - Bohemian
@Bohemian，您能详细说明一下吗？ - brain storm
@Bohemian，简单的跳过是O(n^2)，因为您需要遍历每个项目并检查所有范围。 - Sergey Prosin
1
@Sergey 不需要。我的建议是O(n log n)，其中n是范围的数量。它是O(n log n)，因为您需要对范围进行插入排序。您可以在插入时合并/缩小它们以获得适度的性能提升。 - Bohemian
1
你能提供（伪）代码来演示这个想法吗？ - Sergey Prosin
显示剩余2条评论
6个回答
1

参考@Bohemian的想法，将您的方法从“添加所有元素，然后按范围删除”改为“在删除范围之外添加元素”

  1. Sort the rangesToBeRemoved (by range.start)
  2. Loop over the range and add element that are not cover by ranges

  3. Add all element after the last range's end

    // 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进行排序后，两个范围之间的关系为：

  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)，命中第3种情况，将间隙[0,1]添加到结果集中，并将borderElementIndex更改为7。
  • 接下来，将(-1,7)与(4,6)进行比较，并命中第1种情况，忽略它。
  • 然后，将(-1,7)与(6,8)进行比较，并命中第2种情况，将borderElementIndex更改为8。
  • 最后，将剩余的间隙[9,10]附加到结果集中。
为了进一步减少空间使用，您可以使用@Danny_ds解决方案中的相同想法状态来存储元素的范围，而不是单个元素。
你能计算复杂度吗？我看它是O(n*m)。如果我们使用索引，我们可以避免内部循环，这将得到O(n)的结果。有关详细信息，请参阅我的解决方案。 - Sergey Prosin
1
@SergeyProsin 上述代码的复杂度为O(n+m)，因为它将循环一次所有范围，导致O(m)，并且在最坏的情况下它最多将外部元素循环一次，给出O(n)。除此之外，排序需要O(mlogm)的时间。 - hk6279
为了进一步改进代码，你在第三步做什么？你是在循环更大的范围吗？你能添加说明代码吗？ - brain storm
@brainstorm 更新解决方案并添加说明。 - hk6279
@brainstorm 不，上面的代码在最坏情况下是O(m+n)，在排序方面是O(mlogm)。由于变量“borderElementIndex”，方法“addElements”永远不会添加相同的元素两次。 - hk6279
显示剩余3条评论
1
我的想法是坚持使用索引而不是项值。好处是排除一个范围的操作是O(1)，因为我们只需要更改一个索引值，而不是遍历数组的每个项。 之后，我们应该通过数组索引来编译答案（有关如何构建结果的详细信息，请参见printRange方法）。 至于结果复杂度，解决方案为O(n) + O(m)，其中n是外部范围大小，m是我们想要排除的范围数。在内存使用方面，解决方案为O(n)，因为我们需要使用额外的数组来存储n大小的索引。 预先条件：我们想要排除的所有范围应按range.start值进行排序。如果它们未经排序，则将O(m*log(m))复杂度添加到算法中。
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Arrays;

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

    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); //sorted ranges by range.start
        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);


        printRange(outer, removeRanges(outer, rangesToBeRemoved));

    }

    public static void printRange(Range outer, int[] indexes)
    {
        int outerRangeSize = outer.end - outer.start + 2;
        int rangeShift = - (outer.start - 1);
        int current = 0;

        while (indexes[current] - rangeShift <= outer.end)
        {
            System.out.println(indexes[current] - rangeShift);
            current = indexes[current];
        }

    }

    public static int[] removeRanges(Range outer, List<Range> rangesToBeRemoved ) {
        int outerRangeSize = outer.end - outer.start + 2;
        int rangeShift = - (outer.start - 1);

        int[] outerElementsIndexes = new int[outerRangeSize];

        for (int i = 0; i<outerRangeSize;i++ ){
            outerElementsIndexes[i]=i+1; // construct indexes refereneces to the next indexes (one by one)
        }

        int currentIndex = 0; // point ot the first element in array
        int currentIndexNext = 1;

        for (Range range : rangesToBeRemoved) {
            if (currentIndex >= outerRangeSize) break;
            //int currentIndexNext = outerElementsIndexes[currentIndex];
            int nextIndexStart = range.start + rangeShift - 1; //calculate what index we should start from to exclude the range
            if (nextIndexStart < 0) nextIndexStart = 0;
            int nextIndexEnd = range.end + rangeShift + 1; // where we should jump to
            if (nextIndexEnd <= currentIndexNext) continue; // if we already skipped the range we're trying to exclude
            if (nextIndexStart <= currentIndexNext)
            {
              outerElementsIndexes[currentIndex] = nextIndexEnd; // case where we should extend the excluded range because it's intecepted with the last one we skipped

                currentIndexNext = nextIndexEnd;
            }
            else
            {
              outerElementsIndexes[nextIndexStart] = nextIndexEnd; // just exclude the range
              currentIndex = nextIndexStart;
              currentIndexNext = nextIndexEnd;
            }
        }
        return outerElementsIndexes;
    }
}
1
为了改进您的解决方案，您可以合并区间列表，这是一个经典问题，您可以在此处找到代码：
https://leetcode.com/problems/merge-intervals/discuss/21222/A-simple-Java-solution 然后，您可以保留相同的代码，但它变为O(n)而不是O(n2)，因为所有区间都是不相交的，每个元素最多只出现在一个输入区间中。
作为第二个改进，您可以只检查当前值是否是区间左侧，如果是，则跳过该区间：
public static Set<Integer> removeRanges(Range outer, List<Range> rangesToBeRemoved ) {

    HashMap<Integer, Integer> Ranges = new HashMap<>();
    for (Range range : rangesToBeRemoved) {
        Ranges.put(range.start, range.end);
    }

    Set<Integer> outerElements = new HashSet<>();
    for (int j = range.start; j<=range.end; j++) {
       if(Ranges.get(j))
       {
           int left=j, right=Ranges.get(j);
           j += right - left + 1; //skip this interval
       }
       else
       {
           outerElements.add(j);
       }
    }

    return outerElements;
}
使用 map 函数时，出现额外的空格？ - brain storm
是的，虽然这个映射应该很小，因为它只包含合并的间隔。 - arenard
1

尽管Bogemian的解决方案（注释）可能是最好的（"对范围进行排序，然后使用外部范围的循环跳过范围来输出"），但这里还有一种额外的方法可以完成：

Bigger range: (0,10) 
List of Ranges:  [(2,7),(4,6),(6,8)]

Result list: [(0,10)]

to remove (2,7) split the result list: [(0,1),(8,10)]
(4,6) -> no action
(6,8) -> [(0,1),(9,10)]

这可以在不对范围进行排序的情况下完成，但这意味着我们每次都必须在结果列表中查找位置。
这两种解决方案在处理大范围（如果它们返回一个范围列表而不是包含所有值的列表）时表现良好。
例如：
Bigger range: (0,4000000000) // 4 billion in uint32
List of Ranges:  [(200,1000000),(1000000000,2000000000)]

Result list: [(0,199),(1000001,999999999),(2000000001,4000000000)]

使用的空间很小，执行即时。如果使用一个使用O(n)空间的算法来处理上述范围，其中n是外部范围的大小，将会有问题。

1

我对此的复杂性一无所知，但认为使用Java-8解决这个问题会很有趣：

Set<Integer> set = IntStream.concat(
            IntStream.range(outer.start, outer.end),
            rangesToBeRemoved.stream()
                    .reduce(
                            IntStream.empty(),
                            (stream, range) -> IntStream.concat(stream, IntStream.range(range.start, range.end)),
                            IntStream::concat)
                    .distinct())
            .boxed()
            .collect(Collectors.toMap(Function.identity(), x -> Boolean.TRUE, (x, y) -> null))
            .keySet();
1
我决定发布另一个答案，展示优化后的解决方案，其复杂度为O(1)+O(m)，其中m是范围的数量，因此它不取决于外部范围的大小。但是，它需要O(n)的内存。
它也不使用任何类，应该运行非常快。
欢迎听取评论。
以下是代码：
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Arrays;

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

    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); //sorted ranges by range.start
        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);


        printRange(outer, removeRanges(outer, rangesToBeRemoved));

    }

    public static void printRange(Range outer, int[] indexes)
    {
        int outerRangeSize = outer.end - outer.start + 2;
        int rangeShift = - (outer.start - 1);
        int current = 0;
        int currentNext = ((indexes[current] > 0) ? indexes[current] : current + 1);

        while (currentNext - rangeShift <= outer.end)
        {
            System.out.println(currentNext - rangeShift);
            current = currentNext;
            currentNext = ((indexes[current] > 0) ? indexes[current] : current + 1);
        }

    }

    public static int[] removeRanges(Range outer, List<Range> rangesToBeRemoved ) {
        int outerRangeSize = outer.end - outer.start + 2;
        int rangeShift = - (outer.start - 1);

        int[] outerElementsIndexes = new int[outerRangeSize];

        int currentIndex = 0; // point ot the first element in array
        int currentIndexNext = 1;

        for (Range range : rangesToBeRemoved) {
            if (currentIndex >= outerRangeSize) break;
            int nextIndexStart = range.start + rangeShift - 1; //calculate what index we should start from to exclude the range
            if (nextIndexStart < 0) nextIndexStart = 0;
            int nextIndexEnd = range.end + rangeShift + 1; // where we should jump to
            if (nextIndexEnd <= currentIndexNext) continue; // if we already skipped the range we're trying to exclude
            if (nextIndexStart <= currentIndexNext)
            {
              outerElementsIndexes[currentIndex] = nextIndexEnd; // case where we should extend the excluded range because it's intecepted with the last one we skipped

                currentIndexNext = nextIndexEnd;
            }
            else
            {
              outerElementsIndexes[nextIndexStart] = nextIndexEnd; // just exclude the range
              currentIndex = nextIndexStart;
              currentIndexNext = nextIndexEnd;
            }
        }
        return outerElementsIndexes;
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接