数据流作为C ++中的不相交间隔

假设我们有一个整数的数据流输入,这些整数就像a1,a2,...,an,...,我们必须总结所看到的数字,作为不相交间隔的列表。例如,假设输入整数是1、3、8、2、7,...,则汇总将为-

  • [1,1]

  • [1,1],[3,3]

  • [1,1],[3,3],[8,8]

  • [1,3],[8,8]

  • [1,3],[7,8]。

为了解决这个问题,我们将遵循以下步骤-

  • 设置一个名为nums的集合

  • 在初始化程序中,将low:= -inf和high:= inf设置为

  • 从以num作为输入的addNum方法中,将num插入设置的nums中。

  • 从获取间隔方法中,执行以下操作-

  • 定义一个2D阵列ret

  • 它:=设置数字的开始元素

  • 当它在集合中时,请-

    • 将ret的最后一个元素的索引1处的元素增加1

    • 在ret的末尾插入对{x,x}

    • x:=它的值

    • 如果ret为空或元素位于ret的最后一个元素的索引1 + 1 <x,则,

    • 除此以外

    • 它到下一个元素

    • 返回ret

    示例

    让我们看下面的实现以更好地理解-

    #include <bits/stdc++.h<
    using namespace std;
    void print_vector(vector<vector<auto> > v){
       cout << "[";
       for(int i = 0; i<v.size(); i++){
          cout << "[";
          for(int j = 0; j <v[i].size(); j++){
             cout << v[i][j] << ", ";
          }
          cout << "],";
       }
       cout << "]"<<endl;
    }
    class SummaryRanges {
       public:
       set <int> nums;
       int low, high;
       SummaryRanges() {
          low = INT_MAX;
          high = INT_MIN;
       }
       void addNum(int val) {
          nums.insert(val);
       }
       vector<vector<int>> getIntervals() {
          vector < vector <int> > ret;
          set <int> :: iterator it = nums.begin();
          while(it != nums.end()){
             int x = *it;
             if(ret.empty() || ret.back()[1] + 1 < x){
                ret.push_back({x, x});
             } else {
                ret.back()[1]++;
             }
             it++;
          }
          return ret;
       }
    };
    main(){
       SummaryRanges ob;
       ob.addNum(1);
       print_vector(ob.getIntervals());
       ob.addNum(3);
       print_vector(ob.getIntervals());
       ob.addNum(8);
       print_vector(ob.getIntervals());
       ob.addNum(2);
       print_vector(ob.getIntervals());
       ob.addNum(7);
       print_vector(ob.getIntervals());
    }

    输入值

    Initialize the class, then insert one element at a time and see the intervals. So the elements are [1,3,8,2,7]

    输出结果

    [[1, 1, ],]
    [[1, 1, ],[3, 3, ],]
    [[1, 1, ],[3, 3, ],[8, 8, ],]
    [[1, 3, ],[8, 8, ],]
    [[1, 3, ],[7, 8, ],]