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

参考@Bohemian的想法,将方法从“add all element then remove by range”更改为“add element outofremove range”

1. 对移动的范围进行排序(按范围。开始)
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);
       }
   }
   

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

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

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

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

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

• 接下来,将(-1,7)与(4,6)进行比较并命中案例1,忽略它。
• 然后,将(-1,7)与(6,8)进行比较并命中案例2,将borderElementIndex更改为8。

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

我的想法是坚持索引而不是项目值。这样做的好处是排除一个范围是O(1)的操作,因为不必遍历数组的每一项,我们只需要更改一个索引值。 之后,我们应该遍历数组索引来编译答案(有关如何构造结果的详细信息,请参见printRange方法)。 O(n)+O(m) 哪里 n个 米 是要排除的范围数。就内存而言,使用该解决方案是O(n),因为我们需要使用额外的数组来存储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;

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

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

对范围排序,然后在外部范围上使用循环输出,跳过范围 ),下面是一种额外的方法:

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

我不知道这个问题的复杂性,但认为使用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();

它也不使用任何类,应该工作得很快。

很高兴听到大家的评论。

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