亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定

一種整數區間連續性的判定方法

標簽:
數據結構

0 引言
最近的工作中遇到了这么一个问题,需对任意个整数区间判断其连续性。思考一番后发现一个较为通用的方法,问题虽然不难,但感觉大家或许也会遇到,在此分享一下。
这里的区间连续性分为两个方面,一是区间之间不能出现重叠;二是区间之间不能存在数值间隔。区间本身也存在开区间和闭区间并存的情况,因此,第一步是解决区间开闭情况不统一的问题。
1 开区间转化为闭区间
开区间边界值进行比较时总是感觉隔着一层,索性将所有开区间转为闭区间。这部分的工作比较简单,过程就简单略过。
2 只有两个区间的情况
上学时老师就教导我们,解决复杂问题时要先从简单情况入手,简化模型,寻找规律,最后再从简单情况推广到复杂情况......
嗯,是的,让我们先来考虑只有两个区间时的情况。
我们将连续性分为重叠和间隔两个角度加以考虑。假设,存在整数区间A_1=[a,b],A_2=[c,d],如果A_1、 A_2间隔,必然有max⁡(a,c)-min⁡(b,d)>1;如果区间A_1、 A_2重叠,必然有max⁡(a,c)-min⁡(b,d)≤0。因此,只有当<0max⁡(a,c)-min⁡(b,d)<=1,即max⁡(a,c)-min⁡(b,d)=1时,整数区间A_1、 A_2才连续。

3 任意个区间的情况
我们对max⁡(a,c)-min⁡(b,d)=1进行简单推导,可得出如下结论。
已知整数区间A_1=[a,b],A_2=[c,d],其中,c>a,则,当且仅当c-d=1时区间A_1、 A_2连续。
我们将上述经验推广到任意数量整数区间的情况。假设,存在n个整数区间A_1,A_2,…,A_n,其中任一区间A_i的区间左边界记为A_i.start,右边界记为A_i.end,判断A_1,A_2,…,A_n是否连续。
利用上述结论,将判断过程分为两个步骤:
step1:将区间序列A_1,A_2,…,A_n按照区间左边界(A_i.start)升序排列,得新序列。
step2: 在新序列中,通过循环判断Ai.end+1,是否等于A(i+1).start,(i=1,2,…,n-1)。如果存在不相等的情况,则说明区间序列A_1,A_2,…,A_n不连续;如果都相等,则说明区间序列A_1,A_2,…,A_n连续。
通过伪代码,可将上述过程描述如下:
图片描述

当然,我们也可以对step2中的结论进行简单扩展,如果A_(i+1).start>A_i.end+1,(i=1,2…n-1),则区间Ai和区间A(i+1)间隔;如果A_(i+1).start<A_i.end+1,(i=1,2…n-1),则区间Ai和区间A(i+1)重叠。
至此判断过程就算完成了。

點擊查看更多內容
TA 點贊

若覺得本文不錯,就分享一下吧!

評論

作者其他優質文章

正在加載中
Web前端工程師
手記
粉絲
0
獲贊與收藏
3

關注作者,訂閱最新文章

閱讀免費教程

  • 推薦
  • 評論
  • 收藏
  • 共同學習,寫下你的評論
感謝您的支持,我會繼續努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消