Luồng dữ liệu dưới dạng các khoảng rời rạc trong C ++

Giả sử chúng ta có một luồng dữ liệu đầu vào là các số nguyên, chúng giống như a1, a2, ..., an, ..., chúng ta phải tóm tắt các số được xem như một danh sách các khoảng rời rạc. Ví dụ:giả sử các số nguyên đầu vào là 1, 3, 8, 2, 7, ..., thì tóm tắt sẽ là -

• [1,1]

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

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

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

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

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một tập hợp có tên là nums

• trong trình khởi tạo, đặt thấp:=-inf và cao:=inf

• Từ phương thức addNum lấy num làm đầu vào, hãy chèn num vào tập hợp nums

• Từ phương pháp lấy khoảng thời gian, hãy làm như sau -

• Xác định một mảng 2D ret

• it:=phần tử bắt đầu của tập hợp số

• trong khi nó ở trong bộ, hãy làm -

  • x:=giá trị của nó

  • nếu ret trống hoặc phần tử ở chỉ mục 1 của phần tử cuối cùng của ret + 1

    • chèn cặp {x, x} vào cuối ret

  • Nếu không

    • tăng phần tử có mặt ở chỉ mục 1 của phần tử cuối cùng của ret lên 1

  • nó đến phần tử tiếp theo

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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());
}

Đầu vào

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

Đầu ra

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