设计师找素材的网站_广告设计与制作专升本考什么_百度发布平台官网_网站联盟推广

区间操作相关的算法

1.前言

在个人项目的研究中遇到一个和区间操作相关的场景，涉及到给定一个数，查找对应的区间和查找所有重叠的区间。现对这个问题的算法做个总结。

例1.给定若干个区间：

[1,3],[5,10],[21,26]

然后给定若干个数:0,1,2,3,8,26,29，查找这些数对应的区间，找不到就返回空。预期结果是

null
[1,3]
[1,3]
[1,3]
[5,10]
[21,26]
null

例2.给定若干个区间：

[1,3],[2,6],[10,29],[10,14],[22,78],[100,133]

找出以上区间中所有重叠的区间，找不到返回空。预期结果是

[1,3],[2,6]
[10,29],[10,14]
[10,29],[22,78]

2.算法

2.1.查找区间算法

可以借用二分查找的思想，首先可以在插入区间的时候按顺序插入。借用例1的数据，默认以区间左端点数值从小到大的顺序将区间插入，得到

a = [1,3,5,10,21,26]

对于新的序列有这么两个特点：

1. 偶数位是原区间的左端点，奇数位是原区间的右端点。
2. 序列的长度为偶数。

2.1.2.流程图

所以结合二分查找与序列的特点，就能在O(n) = log(n)的时间复杂度下找到对应区间。

2.1.3.代码实现

$注：使用c++20$

auto find_segment(_Ty number)->std::optional<const IntervalNode<_Ty>>
{int l = 0;int h = m_segments.size() - 1;while (l <= h){int m = (l + h) / 2;if (m & 1){if (number >= m_segments[m - 1] && number <= m_segments[m]){return IntervalNode<_Ty>{.left = m_segments[m - 1],.right = m_segments[m]};}if (number < m_segments[m - 1]) h = m - 1;else if (number > m_segments[m]) l = m + 1;}else{if (number >= m_segments[m] && number <= m_segments[m + 1]){return IntervalNode<_Ty>{.left = m_segments[m],.right = m_segments[m + 1]};}if (number < m_segments[m]) h = m - 1;else if (number > m_segments[m + 1]) l = m + 1;}}return std::nullopt;
}

2.2.查找所有重叠区间的算法

借用前言中提到的例2中的数据，默认以区间左端点和右端点数值从小到大的顺序将区间插入，得到

a = [1,3,2,6,10,14,10,29,22,78,100,133]

对于新的序列有这么两个特点：

1. 偶数位是原区间的左端点，奇数位是原区间的右端点。
2. 序列的长度为偶数。

2.2.1.算法流程图

2.2.2.代码实现

$注：使用c++20$

auto find_all_overlaps()->std::vector<std::tuple<const IntervalNode<_Ty>, const IntervalNode<_Ty>>>
{std::vector<std::tuple<const IntervalNode<_Ty>, const IntervalNode<_Ty>>> findOverlaps;for (int i = 0; i < m_segments.size() / 2 - 1; i++){for (int j = i + 1; j < m_segments.size() / 2; j++){if (m_segments[2 * i] <= m_segments[2 * j] && m_segments[2 * i + 1] >= m_segments[2 * j]){std::tuple<const IntervalNode<_Ty>, const IntervalNode<_Ty>> overlaps{IntervalNode<_Ty>{.left = m_segments[2 * i],.right = m_segments[2 * i + 1]},IntervalNode<_Ty>{.left = m_segments[2 * j],.right = m_segments[2 * j + 1]},};findOverlaps.push_back(overlaps);}}}return findOverlaps;
}

3.测试

class CCIntervalTester
{
public:auto TestFindSegment()->void{Algorithm::CCInterval<int> interval;interval.add_segment(1, 3);interval.add_segment(5,10);interval.add_segment(21,26);srand(time(NULL));for (int i = 0; i < 20; i++){auto r = rand() % 30;const auto& f = interval.find_segment(r);if (f != std::nullopt)printf("%d in [%d,%d]\n", r, f.value().left, f.value().right);else printf("%d not found.\n",r);}}auto TestFindAllOverlaps()->void{Algorithm::CCInterval<int> interval;interval.add_segment(1, 3);interval.add_segment(2, 6);interval.add_segment(10, 29);interval.add_segment(10, 14);interval.add_segment(22, 78);interval.add_segment(100, 133);const auto& o = interval.find_all_overlaps();for (const auto& i : o){printf("[%d,%d] and [%d,%d]\n",std::get<0>(i).left, std::get<0>(i).right,std::get<1>(i).left, std::get<1>(i).right);}}
};

完整代码请移步至我的github：https://github.com/singlefreshBird/Algorithm