给定一个数字流，比如1,3,5,4,6,9，我被要求以1,3-6,9的方式打印它们

Question

给定一个数字流，比如1,3,5,4,6,9，我被要求打印1,3-6,9。我的方法是在maxHeap中保存最少2个数字，在minHeap中保存最多2个数字。我提出了以下解决方案。你有什么建议可以让它更优化吗？其时间复杂度为O(nlogn)。

   public static ArrayList<Integer> mergingMiddleNums (int[] arr){

    if (arr == null || arr.length < 3){
        throw new IllegalArgumentException();
     }

     ArrayList<Integer> result = new ArrayList<>();
     Queue<Integer> minHeap = new PriorityQueue<>(); 

     Queue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
         @Override
            public int compare(Integer num1, Integer num2) {
                return num2-num1;
            }
        });

    for (int i = 0 ; i < 2 ; i++){
        minHeap.add(arr[i]);
    }
    for (int i = 0 ; i < 2 ; i++){
        maxHeap.add(arr[i]);
    }

    for (int i = 2 ; i <arr.length; i++){

        if(arr[i] > minHeap.peek()){
             minHeap.poll();
             minHeap.add(arr[i]);
        }
    }       
     result.add(minHeap.poll());
     result.add(minHeap.poll());


     for (int i = 2 ; i <arr.length; i++){

         if(arr[i] < maxHeap.peek()){
             maxHeap.poll();
             maxHeap.add(arr[i]);             

        }
    }

    result.add(maxHeap.poll());
    result.add(maxHeap.poll());

    Collections.sort(result);
    return result;

   }

Answer 1

这取决于您的输出是否需要流式处理。让我们从非流输出开始，因为您当前的实现解决了这个问题。

您的代码的总体复杂度充其量是O(nLog(n))，但是您可以通过将每个传入数字存储在集合中、将其转换为数组并对其进行排序，然后按顺序扫描这些项来标识连续的范围，从而从根本上简化实现。这里开销最大的操作是sort，它将定义您的运行时。为了节省空间，您可以使用集合或堆集合来避免存储重复项(其形式将接近O(nLog(N)-它们是相同的运行时，在总运行时O(nLog(n))时保持折叠状态。

如果您的代码期望与输出一起流式打印，即打印形成的范围并在遇到的下一个数字与当前范围不直接相邻时移动到下一个范围，则可以在O(n)中执行此操作，方法是在执行时存储当前范围的数值边界，如果当前检查的数字不相邻或在边界内，则打印并重置它们，或者扩展边界(如果是)。

Answer 2

一种可能的实现是使用哈希表来存储每个整数是否出现在输入值中。然后，只需从最小值迭代到最大值，然后使用哈希表找出数字集群的位置。

这样的实现基本上是O(n)，其中n=max-min (而不是列表中的项数)。因此，如果您在一个相当小的值范围内有许多数字，那么您可能比基于排序的方法更好。

import java.util.HashMap;
import java.util.Map;

class Test {
private int min=0, max=-1;
private Map<Integer,Integer> map=new HashMap<Integer,Integer>();

public static void main(String args[]) {
    int[] input={1,3,5,4,6,9};
    Test t = new Test();
    t.readNumbers(input);
    t.outputRanges();
}


public void readNumbers(int[] values) {
    // Get min and max values, and store all existing values in map
    for(int v:values) {
        if(first || v<min) min=v;
        if(first || v>max) max=v;
        first=false;
        map.put(v, 1);
     }
}

public void outputRanges() {
    // Iterate from min to max and use map to find out existing
    // values
    int last=min-2;
    boolean inRange=false;
    first=true;

    for(int i=min;i<=max;++i) {
        if(map.get(i)==null) continue;

        if(i==last+1) {
            inRange=true;
        } else {
            if(inRange) {
                closeRange(last);
                inRange=false;
            }
            output(i);
        }

        last=i;
    }

    if(inRange) closeRange(last);
}

private boolean first;
private void commaUnlessFirst() {
    if(!first) System.out.printf(",");
    first=false;
}
private void output(int i) {
    commaUnlessFirst();
    System.out.printf("%d", i);
}
private void closeRange(int i) {
    System.out.printf("-%d", i);
}
}