实际上interval merge的问题,很容易就可以想到要用hashmap来记录每个interval的起点和终点。对于一个数i,我们每次需要去map中找以i - 1结尾的interval和i + 1开头的interval然后做相应的更新,同时还需要去重。那代表我们需要两个hashmap来分别记录头尾,一个set用来去重。但是我们真的需要这么用这么多数据结构吗?事实上如果稍微仔细地思考一下,就会发现一个hash map可以完美满足我们的所有需求。我们用map记录以下的东西
- 如果i为某个interval的起点或者终点,那么map[i]记录interval的长度
- 否则,map[i]的值无关紧要,map对于这些i的作用是去重,已经考虑过的i就不需要再考虑了
那么很显然,这样的一个map完全就够用了。对于新插入的i,有以下几种情况:
- i已经在map里,跳过
- i -1和i + 1都不在map里,i自己形成了一个interval,map[i] = 1;
- i - 1和i + 1只有其中一个在map中,那么相应的我们插入i可以让已经在map中的某个interval向左或者向右扩展,假设扩展前长度为len,map[i] = len + 1,map[i - len] = len + 1
- i - 1和i + 1都在map中,那么我们可以讲原本在map中的interval merge成一个更长的interval,假设原本在左边的interval长len1,右边的长len2,那么map[i - len] = len1 + len2 + 1, map[i + len] = len1 + len2 + 1, map[i]的值随意
我们同时记录最长的interval,那么最后的结果就是我们要的Longest Consecutive Sequence。时间负责度O(n),空间复杂度O(n),代码如下:
No comments:
Post a Comment