首页 > 笔试面试题 > 线段覆盖长度

线段覆盖长度

2012年7月16日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

给定一些线段,线段有起点和终点,求这些线段的覆盖长度,重复的部分只计算一次。

这是在小桥流水博客中看到的一道面试题(小米科技),后来为了练习线段树这个数据结构,就做了一下这道题,本节给出两种方法,一种是基于排序来做的,一种是使用线段树来做的。

方法一:

首先说排序对于处理很多问题都是非常有效的,例如寻找兄弟单词等问题中,经过排序处理后,问题就明朗了很多;

线段覆盖长度也是这样,将线段排序后,然后扫描一遍就可以得到覆盖的长度。具体做法:排序时,先按线段的起始端点排序,如果始点相同则按照末端点排,然后从头扫描,寻找连续段;所谓连续段即下一条线段的始点不大于当前线段的末点就一直扫描,直到找到断层的,计算当前长度,然后继续重复扫描直到最后,便得总长度。代码如下:

#include<iostream>
using namespace std;

/* 排序求线段覆盖长度 */
#define MAXN 100   // 设线段数不超过100

struct segment
{
	int start;
	int end;
}segArr[100];

/* 计算线段覆盖长度 */
int lenCount(segment * segArr, int size)
{
	int length = 0, start = 0, end = 0;
	for(int i = 0; i < size; ++i)
	{
		start = segArr[i].start;
		end = segArr[i].end;
		while(end >= segArr[i+1].start)
		{
			++i;
			end = segArr[i].end > end ? segArr[i].end : end;
		}
		length += (end - start);
	}
	return length;
}

/* 快排比较函数 */
int cmp(const void * p, const void *q)
{
	if(((segment *)p)->start != ((segment *)q)->start)
	{
		return ((segment *)p)->start - ((segment *)q)->start;
	}
	return ((segment *)p)->end - ((segment *)q)->end;
}

/* 测试线段 answer: 71 */
int segTest[10][2] = {
	5, 8,	10, 45,	   0, 7,
	2, 3,	 3, 9,	  13, 26,
   15, 38,  50, 67,	   39, 42,
   70, 80
};

void main()
{
	for(int i = 0; i < 10; ++i)           // 测试线段
	{
		segArr[i].start = segTest[i][0];
		segArr[i].end = segTest[i][1];
	}
	qsort(segArr,10,sizeof(segment),cmp);       // 排序
	printf("length: %d\n",lenCount(segArr,10)); // 计算
}

方法二:

当我学习线段树这个数据结构时,百度谷歌一番,发现关于它的资料真是铺天盖地,而线段树的经典应用就是求线段覆盖长度了,线段树本身的数据结构很简单,关键在于怎么用,线段结构如何设计,查询、更新等操作如何具体问题具体处理,这里就不列举了,改天多做几道题练练手。对于本题,在插入线段的时候,标记覆盖,之后统计总长度便可。直接上代码:

#include<iostream>
using namespace std;

/* 线段树求线段覆盖长度 */
#define BORDER 100  // 设线段端点坐标不超过100

struct Node         // 线段树
{
	int left;
	int right;
	int isCover;    // 标记是否被覆盖
}segTree[4*BORDER];

/* 构建线段树 根节点开始构建区间[lef,rig]的线段树*/
void construct(int index, int lef, int rig)
{
	segTree[index].left = lef;
	segTree[index].right = rig;
	if(rig - 1 == lef)                 // 到单位1线段
	{
		segTree[index].isCover = 0;
		return;
	}
	int mid = (lef+rig) >> 1;
	construct((index<<1)+1, lef, mid);
	construct((index<<1)+2, mid, rig); // 非mid+1,线段覆盖[mid,mid+1]
	segTree[index].isCover = 0;
}

/* 插入线段[start,end]到线段树, 同时标记覆盖 */
void insert(int index, int start, int end)
{
	if(segTree[index].isCover == 1)	return; // 如已覆盖,没必要继续向下插

	if(segTree[index].left == start && segTree[index].right == end)
	{
		segTree[index].isCover = 1;
		return;
	}
	int mid = (segTree[index].left + segTree[index].right) >> 1;
	if(end <= mid)
	{
		insert((index<<1)+1, start, end);
	}else if(start >= mid)             // 勿漏=
	{
		insert((index<<1)+2, start, end);
	}else
	{
		insert((index<<1)+1, start, mid);
		insert((index<<1)+2, mid, end);
		// 注:不是mid+1,线段覆盖,不能漏[mid,mid+1]
	}
}

/* 计算线段覆盖长度 */
int Count(int index)
{
	if(segTree[index].isCover == 1)
	{
		return segTree[index].right - segTree[index].left;
	}else if(segTree[index].right - segTree[index].left == 1)
	{
		return 0;
	}
	return Count((index<<1)+1) + Count((index<<1)+2);
}

/* 测试线段 answer: 71 */
int segment[10][2] = {
	5, 8,	10, 45,	   0, 7,
	2, 3,	 3, 9,	  13, 26,
   15, 38,  50, 67,	   39, 42,
   70, 80
};

void main()
{
	construct(0,0,100);           // 构建[0,100]线段树
	for(int i = 0; i < 10; ++i)   // 插入测试线段
	{
		insert(0,segment[i][0],segment[i][1]);
	}
	printf("the cover length is %d\n", Count(0));
}

总结:

基于排序的方法,由于排序的缘故,复杂度为O(nlgn);使用线段树时,因其查询和插入操作都可以在lgn的时间完成,故对于所有线段完成插入,最后查询长度,算法总的复杂度也是O(nlgn)级别。

本文相关代码可以到这里下载。

(全文完)

参考资料:

http://smallbridge.sinaapp.com/124110.html

http://baike.baidu.com/view/670683.htm

杨弋讲稿《线段树》

  • http://www.qrwen.com varequan

    @cjw
    數組下標從0開始左孩子便是(index<<1)+1,右孩子是(index<<1)+2

    • Yx.Ac

      谢谢帮忙解答 :-)

  • cjw

    insert((index<<1)+1, start, mid);
    insert((index<<1)+2, mid, end);

    为什么插入时候不是(index<<1)和(index<<1)+1

    • Yx.Ac

      正如@varequan 所说 O(∩_∩)O~