题目

类型：Design
image.png

解题思路

image.png

image.png

代码

  1. class SummaryRanges {
  2.     TreeMap<Integer, Integer> intervals;
  4.     public SummaryRanges() {
  5.         intervals = new TreeMap<Integer, Integer>();
  6.     }
  8.     public void addNum(int val) {
  9.         // 找到 l1 最小的且满足 l1 > val 的区间 interval1 = [l1, r1]
  10.         // 如果不存在这样的区间，interval1 为尾迭代器
  11.         Map.Entry<Integer, Integer> interval1 = intervals.ceilingEntry(val + 1);
  12.         // 找到 l0 最大的且满足 l0 <= val 的区间 interval0 = [l0, r0]
  13.         // 在有序集合中，interval0 就是 interval1 的前一个区间
  14.         // 如果不存在这样的区间，interval0 为尾迭代器
  15.         Map.Entry<Integer, Integer> interval0 = intervals.floorEntry(val);
  17.         if (interval0 != null && interval0.getKey() <= val && val <= interval0.getValue()) {
  18.             // 情况一
  19.             return;
  20.         } else {
  21.             boolean leftAside = interval0 != null && interval0.getValue() + 1 == val;
  22.             boolean rightAside = interval1 != null && interval1.getKey() - 1 == val;
  23.             if (leftAside && rightAside) {
  24.                 // 情况四
  25.                 int left = interval0.getKey(), right = interval1.getValue();
  26.                 intervals.remove(interval0.getKey());
  27.                 intervals.remove(interval1.getKey());
  28.                 intervals.put(left, right);
  29.             } else if (leftAside) {
  30.                 // 情况二
  31.                 intervals.put(interval0.getKey(), interval0.getValue() + 1);
  32.             } else if (rightAside) {
  33.                 // 情况三
  34.                 int right = interval1.getValue();
  35.                 intervals.remove(interval1.getKey());
  36.                 intervals.put(val, right);
  37.             } else {
  38.                 // 情况五
  39.                 intervals.put(val, val);
  40.             }
  41.         }
  42.     }
  44.     public int[][] getIntervals() {
  45.         int size = intervals.size();
  46.         int[][] ans = new int[size][2];
  47.         int index = 0;
  48.         for (Map.Entry<Integer, Integer> entry : intervals.entrySet()) {
  49.             int left = entry.getKey(), right = entry.getValue();
  50.             ans[index][0] = left;
  51.             ans[index][1] = right;
  52.             ++index;
  53.         }
  54.         return ans;
  55.     }
  56. }