找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 11829|回复: 21
收起左侧

[米群网刷题小分队] [leetcode] Missing Ranges

  [复制链接]
发表于 2-21-2016 02:15 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 cpcs 于 12-10-2014 01:02 AM 编辑

题目:Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].


分析:只要沿着区间lower扫一次即可。我们维持一个循环不变式: 目前[lower..upper]是不确定有没有在数组里出现的。A[]中小于lower的都已经决定好了。

于是有三种情况:

(1) A【i】 < lower, 因为小于lower的都考虑过了,所以A【i】这个数不影响结果。

(2) A【i】 == lower, 显然lower = lower + 1,继续考虑。

(3) A【i】 > lower, 这说明[lower..A【i】 - 1]是缺失的区间。然后我们输出lower..A【i】 - 1,然后lower = A【i】 + 1。

三种情况下,都能维持我们的循环不变式。写出的代码简短、清晰易懂,更容易考虑边界条件(第一个,最后一个等)。

我觉得循环不变式,可以简化问题,请仔细理解循环不变式的思想。

代码:

  1. class Solution {
  2. public:
  3.     string make(int from, int to) {
  4.         ostringstream temp;
  5.         temp << from;
  6.         if (from < to) {
  7.             temp << "->" << to;
  8.         }
  9.         return temp.str();
  10.     }
  11.     vector<string> findMissingRanges(int A[], int n, int lower, int upper) {
  12.         int i;
  13.         vector<string> answer;
  14.         for (i = 0; (i < n) && (lower <= upper) && (A【i】 <= upper); ++i) {
  15.             if (A【i】 > lower) {
  16.                 // lower..A【i】 - 1
  17.                 answer.push_back(make(lower, A【i】 - 1));
  18.                 lower  = A【i】 + 1;
  19.             }
  20.             else if (A【i】 == lower) {
  21.                 ++lower;
  22.             }
  23.         }
  24.         if (lower <= upper) {
  25.             answer.push_back(make(lower, upper));
  26.         }
  27.         return answer;
  28.     }
  29. };
复制代码

时间复杂度 : O(n)

陷阱:注意当缺失的区间仅仅是一个数的时候,没有剪头"->",还有最后一个缺失区间的处理。





评分

参与人数 1金钱 +21 收起 理由
admin + 21 很给力!

查看全部评分

本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

4

主题

1

精华

221

积分

高级会员

Rank: 3Rank: 3

积分
221
发表于 2-21-2016 09:24 PM | 显示全部楼层
怒顶曹神~~~~~~~~~~~
回复

使用道具 举报

12

主题

4

精华

243

积分

高级会员

Rank: 3Rank: 3

积分
243
发表于 2-22-2016 12:05 AM | 显示全部楼层
赞一个····
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表