将数据流变为多个不相交区间

发表于 | 分类于 ， | 评论： | 阅读次数：

将数据流变为多个不相交区间

题目

给定一个非负整数的数据流输入a1，a2，…，an，…，将到目前为止看到的数字总结为不相交的区间列表。

例如，假设数据流中的整数为 1，3，7，2，6，…，每次的总结为：

1
2
3
4
5
[1, 1]
[1, 1], [3, 3]
[1, 1], [3, 3], [7, 7]
[1, 3], [7, 7]
[1, 3], [6, 7]

分析

很明显，题目中涉及到数据的插入，数据的排序，数据区间的合并。

  1. 当插入的数据在已存在的数据区间时，不插入，例如已存在[1, 4]，则不管数据流中会出现的1, 2, 3, 4;
  2. 当插入的数据不在已存在的数据区间时，插入该数据，怎么插？
    2.1 首先插入的数据按顺序排列，每输入一个新的数据，找到其在数据区间列表中的位置；
    2.2 其次，若其位置前后位置的数据都不与此数据相邻（相差1），则插入两个重复的数据；
    2.3 若其位置前后位置的数据与此数据相邻，则做区间合并，

代码

按照分析，首先用c实现了一波

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
typedef struct {
    int *A;
    int n;
    int c; // capacity

} SummaryRanges;

/** Initialize your data structure here. */

SummaryRanges* summaryRangesCreate() {
    SummaryRanges *ranges = (SummaryRanges*)malloc(sizeof(SummaryRanges));
    ranges->c = 10;
    ranges->n = 0;
    ranges->A = (int*)malloc(sizeof(int)*ranges->c);
    return ranges;
}

void summaryRangesAddNum(SummaryRanges* obj, int val) {
    if (obj->c == obj->n) { //如果容量满了，扩充2倍
        obj->c = 2 * obj->c;
        int* B = (int*)malloc(sizeof(int)*obj->c); //创建一个数组B，将A的数据copy给B，然后丢弃A，将结构体List指向B的首地址
        for (int i = 0; i < obj->n; ++i) {
            B[i] = obj->A[i];
        }
        free(obj->A);
        obj->A = B;
    }

    int size = obj->n;
    int start = 0, end = size;
    while (start < end) {            //找到待插入的位置
        int mid = (start + end)/2;
        if (obj->A[mid] <= val) {
            start = mid+1;
        } else {
            end = mid;
        }
    }

    bool left = false, right = false;
    if ((start & 1) == 0) {
        if (start < size && obj->A[start] - 1 == val) { //右相邻
            obj->A[start] = val;
            right = true;
        }
        if (start > 0 && obj->A[start-1] + 1 == val) {  //左相邻
            obj->A[start-1] = val;
            left=true;
        }
        if (!left && !right) {                          //左右不相邻
            for (int i = size+1; (i > start+1)&&(start < size); i--) {
                obj->A[i] = obj->A[i-2];
            }
            obj->A[start] = val;
            obj->A[start+1] = val;
            obj->n = obj->n + 2;
        }

        if (start > 0 && start < obj->n && obj->A[start] == obj->A[start-1]) {   //左右都相邻
            for (int i=start-1; i < obj->n-2; i++) {
                obj->A[i] = obj->A[i+2];
            }
            obj->n = obj->n - 2;
        }
    }
    return;
}

int** summaryRangesGetIntervals(SummaryRanges* obj, int* retSize, int** retColSize) {
    int a[obj->n][2];
    int i = 0, j = 0;
    while (j < obj->n) {
        a[i][0] = obj->A[j];
        a[i][1] = obj->A[j+1];
        j = j+2;
        i = i+1;
    }

    printf("[");
    for (int i=0; i<obj->n/2; i++) {
        printf("[%d, " , a[i][0]);
        printf("%d], " , a[i][1]);
    }
    printf("]\n");
    return a;
}

void summaryRangesFree(SummaryRanges* obj) {
    free(obj->A);
    free(obj);
}

/**
 * Your SummaryRanges struct will be instantiated and called as such:
 * SummaryRanges* obj = summaryRangesCreate();
 * summaryRangesAddNum(obj, val);

 * int** param_2 = summaryRangesGetIntervals(obj, retSize, retColSize);

 * summaryRangesFree(obj);
*/

已完成
执行用时: 4 ms
输入:
["SummaryRanges","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals","addNum","getIntervals"]
[[],[1],[],[3],[],[7],[],[2],[],[6],[]]
输出:
[null,null,[],null,[],null,[],null,[],null,[]]
预期结果:
[null,null,[[1,1]],null,[[1,1],[3,3]],null,[[1,1],[3,3],[7,7]],null,[[1,3],[7,7]],null,[[1,3],[6,7]]]
stdout:

1
2
3
4
5
[[1, 1], ]
[[1, 1], [3, 3], ]
[[1, 1], [3, 3], [7, 7], ]
[[1, 3], [7, 7], ]
[[1, 3], [6, 7], ]

按照我的打印，实现应该是没问题的，不知道为什么输出一直是空，和预期结果对不上，所以用python实现一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class SummaryRanges:
    def __init__(self):
        self.d = []

    def addNum(self, val: int) -> None:
        right = False
        left = False
        m = bisect.bisect(self.d, val)                   #二分查找插入坐标
        if m % 2 == 0:
            if m < len(self.d) and self.d[m] - 1 == val: #如果跟右侧区间差值为1时就直接更新右侧区间，为0时不会插入在这里，所以只判断1
                self.d[m] = val
                right = True
            if m > 0 and self.d[m-1] + 1 == val:         #如果跟左侧区间差值为1时就直接更新左侧区间
                self.d[m-1] = val
                left = True

            if not left and not right:
                self.d.insert(m, val)                    #如果跟区间不相邻就插入区间
                self.d.insert(m, val)
            if m > 0 and m < len(self.d):
                if self.d[m] == self.d[m - 1]:           #根据现有情况选择是否区间合并
                    self.d.pop(m)
                    self.d.pop(m - 1)

    def getIntervals(self) -> List[List[int]]:
        return zip(self.d[:: 2], self.d[1:: 2])         #按奇偶顺序打包输出