C++-映射查找的问题

C++-映射查找的问题

虐人心 发布于 2017-07-11 字数 349 浏览 1137 回复 2

start end location
1000 1050 区域1
3000 4000 区域2
4500 5080 区域3
5090 6800 区域4
7800 9000 区域5
……
这样一个需求,给定一个数字,如果位于start,end之间则返回区域,用什么样的数据结构和方法速度效率高一些?
start,end互不交叉但是数字比较敏感,是明确意义。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

灵芸 2017-09-17 2 楼

struct MetaData
{
uint32 nStart_;
std::string sLocation_;
};
typedef std::map<uint32, MetaData*> LocationMap;
LocationMap lmp;
// 数据初始化操作,数据项中的end作为key
// 查找操作
LocationMap::iterator iter = lmp.upper_bound(someNumber);
//根据需求确定开闭区间,微调整"找到"的判定条件
if (iter!=lmp.end()) {/*返回sLocation_*/}

虐人心 2017-09-07 1 楼

目前来看你这个区域是不连续的,你可以把它补填为连续的为连续的

start end location
0 1000 未知
1000 1050 区域1
1050 3000 未知
3000 4000 区域2
4000 4500 未知
4500 5080 区域3
5080 5090 未知
5090 6800 区域4
6800 7800 未知
7800 9000 区域5

这样你可以把数组设计成这样
$arr=array(1000=>'未知',1050=>'区域1',3000=>'未知',4000=>'区域2',4500=>'未知',5080=>'区域3',5090=>'未知',6800=>'区域4',7800=>'未知',9000=>'区域5');
你可以用二分法或其他算法查找,当数值小于数组的键值并且对应的值不为'未知',就是你要找的区域。