这是清华大学《数据结构》课程期末考试的第一道编程题，我在这篇文章中记录了我从头到尾解题的思维过程和对怎样解题的思考。
1. 题目描述
描述
数轴上有n个点，对于任一闭区间 [a, b]，试计算落在其内的点数。
输入
第一行包括两个整数：点的总数n，查询的次数m。
第二行包含n个数，为各个点的坐标。
以下m行，各包含两个整数：查询区间的左、右边界a和b。
输出
对每次查询，输出落在闭区间[a, b]内点的个数。
样例
input
5 2 1 3 7 9 11 4 6 7 12
output
0 3
限制
-
0 ≤ n, m ≤ 5*10^5
-
对于每次查询的区间[a, b]，都有a <= b
-
各点的坐标互异
-
各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数
-
时间：2 sec
-
内存：256 MB
2. 最简单粗暴的方法
要想解决问题，首先要理解问题。未知量是什么？已知数据是什么？条件是什么？从这道题来看，未知量就是区间内点的个数；已知数据是数轴上的n个点和一个闭区间[a, b]；条件如下：
- n和m是不大于5*10^5次方的非负整数
- 闭区间[a, b]保证a <= b，也就是闭区间左端点有可能等于右端点
- 数轴上的n个点互不相等，不会出现相等的元素，这里暗示数轴上的点构成了一个点的集合（是不是可以利用一些集合的性质？）
- 点的坐标，区间的边界a、b都是小于10^7的非负整数，这里暗示点和区间边界的取值都限定在一个固定范围内
- 算法运行的时间必须在2s内
- 算法占用的空间不得大于256MB
给定数轴上点的集合S和闭区间[a, b]，求S在[a, b]中点的个数。可以马上想到的一种未知量和已知数据之间的联系是：遍历集合S上的每一个点s，检查s是不是满足条件a <= s <= b，如果是则计数，最后得到的计数值count就是要求的结果。还可以做一点小的“优化”：我将S中比a小的元素逐一排除，然后再对比剩下的元素并计数，于是就有了如下的代码：
// 算法1
#include <iostream>
using namespace std;
int range(int *pInt, int n, int a, int i);
int main() {
int n, m;
cin >> n >> m;
int *points = new int[n];
int *answer = new int[m];
for (int i = 0; i < n; i++) {
cin >> points[i];
}
int a, b;
for (int i = 0; i < m; i++) {
cin >> a >> b;
answer[i] = range(points, n, a, b);
}
for (int i = 0; i < m; i++) {
cout << answer[i] << endl;
}
delete[] points;
delete[] answer;
return 0;
}
// 核心算法
int range(int *pInt, int n, int a, int b) {
// 先排除掉所有小于a的元素
int *ptr = pInt;
while (*ptr < a && ptr < pInt + n) {
ptr++;
}
// 对剩下的元素进行计数并返回结果
int count = 0;
for (; ptr < pInt + n; ptr++) {
if (a <= *ptr && *ptr <= b) {
count++;
}
}
return count;
}
毫无疑问地，如此brute-force的方法提交到OJ，只得了55分——OJ提供了20个测试用例，每个5分，除了前面11个通过了，剩下的9个全部超时了。那么上面的这个算法有什么问题呢？仔细观察并思考后不难发现，我们所做的这种“优化”其实是徒劳的：算法仍然针对每个[a, b]遍历了整个数轴上的点，并一一做了比较。如果我们有m个闭区间，点集S大小为n，那么算法1的效率就是O(m * n)，这显然是无法接受的。
而且，算法1还有一个隐含的问题。仔细想想，题目条件中并没有说输入的数轴上的点是有序的，而算法1却隐含假定了points数组中的元素是按单调递增的顺序排列的，这显然不对。况且，这个解决方案并没有将题目中所有的条件都用上。看来我们还得继续深入思考。
3. 第一次尝试改进
虽然简单粗暴的算法并不满足题目要求，但它也不是完全没有意义，它是我们改进算法的起点。此后产生的任何改进版本，其效率都会优于它。通过分析算法1这个简单粗暴的版本，我们可以发现它的问题就在于对数轴上的每个元素都做了一一比较，算法一次只能前进一小步，亦步亦趋。有很多比较是无效的。所以一种改进算法的思路就是减少比较的次数。如果算法1做了100次比较，而经过优化后的算法只比较10次，那么效率就大大提高了。
如果已知数据和未知量之间并没有看上去那么直接的联系，那么我们就要找与之相关的辅助题目，通过解决辅助题目来解决原题。就好比中学的时候解几何题，我们是通过作辅助线将原题转化为与之相关的一道辅助题目进行求解一样。
观察未知量：数轴上的点在闭区间[a, b]范围内的点的个数。对于数轴上的点[1, 3, 7, 9, 11]，要求[7, 12]上点的个数，首先看大于等于区间左端点7的元素有哪些：[7, 9, 11]，再看小于等于区间右端点12的元素有哪些：[1, 3, 7, 9, 11]，它们的交集是：[7, 9, 11]，所以结果是3。也就是说：
- 找到大于等于区间左端点7的最小元素7
- 找到小于等于区间右端点12的最大元素11
- 统计数轴上在7和11之间的元素个数，得到3
我们其实是分别找了区间左端点a和区间右端点b在数轴上的位置，然后通过位置来确定元素个数的。找某个元素在有序数组中的索引位置（又叫秩），你能想到一种与它有关的算法吗？有了！二分查找法不就擅长处理这样的问题吗？嗯！看来这个点值得深挖！那我们能利用它的方法，还是结果？对于这道题而言，既利用了方法又利用了结果。我们知道，相比线性查找O(n)，它的时间复杂度是O(logn)，优化效果明显（这里开始调动基础知识），因此方向应该是正确的；而二分搜索法，恰恰适合用来快速定位元素在数组中的位置（哪怕它并不存在于数组中）。于是，我们写出如下算法：
// 算法2
#include <iostream>
#include <cstdlib>
using namespace std;
int range(int *pInt, int n, int a, int b);
int comp(const void *a, const void *b);
int *find_first_gte(int *pInt, int l, int r, int t);
int *find_first_lte(int *pInt, int l, int r, int t);
int main() {
int n, m;
cin >> n >> m;
int *points = new int[n];
int *answer = new int[m];
for (int i = 0; i < n; i++) {
cin >> points[i];
}
int a, b;
for (int i = 0; i < m; i++) {
cin >> a >> b;
answer[i] = range(points, n, a, b);
}
for (int i = 0; i < m; i++) {
cout << answer[i] << endl;
}
delete[] points;
delete[] answer;
return 0;
}
int range(int *pInt, int n, int a, int b) {
// 先对数组做一个排序
qsort(pInt, n, sizeof(int), comp);
// 找有序数组中，第一个大于等于a的元素
int *p1 = find_first_gte(pInt, 0, n-1, a);
// 找有序数组中，第一个小于等于b的元素
int *p2 = find_first_lte(pInt, 0, n-1, b);
// 通过手写结果并进行大量观察归纳总结可知，下面这个值就是我们想要的结果
return (p2 - p1) + 1;
}
int *find_first_lte(int *pInt, int l, int r, int t) {
int *pos = nullptr;
// 借鉴了二分搜索的思路，定位元素的位置，并返回代表该位置的指针，下同
while (l <= r) {
int m = (l + r) / 2;
if (t == pInt[m]) {
pos = pInt + m;
break;
} else if (t < pInt[m]) {
r = m - 1;
pos = pInt + r;
} else {
l = m + 1;
pos = pInt + m;
}
}
return pos;
}
int *find_first_gte(int *pInt, int l, int r, int t) {
int *pos = nullptr;
while (l <= r) {
int m = (l + r) / 2;
if (t == pInt[m]) {
pos = pInt + m;
break;
} else if (t < pInt[m]) {
r = m - 1;
pos = pInt + m;
} else {
l = m + 1;
pos = pInt + l;
}
}
return pos;
}
int comp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
把算法2提交到OJ，满怀期待地等待结果。一看，大失所望！还是55分，怎么回事，怎么优化后的算法居然和算法1得到的是一样的分数？！仔细检查了一下代码，发现一个问题，我把qsort写到range函数中了，也就是说每次执行我都要毫无意义地把points数组重新排序一遍，这是没有必要的！将它移动到main函数中，只排序一次：
int main() {
int n, m;
cin >> n >> m;
int *points = new int[n];
int *answer = new int[m];
for (int i = 0; i < n; i++) {
cin >> points[i];
}
qsort(points, n, sizeof(int), comp);
int a, b;
for (int i = 0; i < m; i++) {
cin >> a >> b;
answer[i] = range(points, n, a, b);
}
for (int i = 0; i < m; i++) {
cout << answer[i] << endl;
}
delete[] points;
delete[] answer;
return 0;
}
再次提交OJ系统，分数提高到了90，有进步！但还有2个测试用例超时了。要拿到100分，真心不容易！
4. 无头苍蝇闪亮登场
我开始有点心急了。仔细检查了一下算法，我已经用了快速排序算法qsort，以及二分查找法，前者的复杂度是O(nlogn)，后者的效率是O(logn)。对于m个闭区间而言，总的就是O(nlogn+mlogn) = O(nlogn)，效率已经不差了。难道还不满足题目要求？
那我们还有什么可优化的空间吗？算法2的解决方案为了找元素的秩，将整个数轴上的点进行了排序，能不能不排序找到元素的秩？这使我想到了快速排序算法中的partition方法，它的效率大约在1.35logn左右。试过之后发现分数仍然是90分，没有效果。
终于还是忍不住上网搜了一下别人的答案，发现有人提出可以根据“各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数”这一条件，使用计数排序来对数组进行排序。这个算法针对有特定取值范围的数进行排序能达到O(n)的复杂度，要优于快速排序的O(nlogn)，于是我自己写了个计数排序算法，好家伙，不但效率没提高，还喜提了一个错误结果，变成了85分。
在此之后，我进行了各种猜测，各种尝试，得到的分数也琳琅满目：80分、15分、0分……90分就像一个无法逾越的障碍，挡在我前进的道路上。我开始有点烦躁了，像个无头苍蝇一样这试试那试试。连猜带蒙，都无一例外全部失败了。晚上加班回家9点过，洗完澡开始解题到12点过，早上六点过起床，再解题，然后再匆匆忙忙跑去上班，甚至一边开车还在一边琢磨自己到底错在哪？
5. 重新冷静下来
一直这样下去并不是办法，我必须先冷静下来，然后再仔细思考。首先，大方向上思路有没有问题？没有问题！网上别人的答案也是“排序+二分查找”的整体思路。我将这个问题拆解为排序和（二分）查找的解决方案是正确的。
那么只可能是“排序”或者“二分查找”的算法有问题了！这个可能性很大，因为计数排序和二分查找都是我写的，并没有经过充分的测试！Wrong Answer就是我在替换了自己写的计数排序算法后出现的，肯定写的有问题！
另外，在网上参考别人的实现思路的过程中，我发现有人也用qsort圆满解决了问题，还有人自己手写归并排序的，说明使用qsort并不是导致超时的原因。而且某个人在他的博客中提到，要用C语言的scanf和printf进行输入输出，不要用C++的cin和cout，前者效率更高。难道是这个原因导致超时？我试验了一下，果然，分数提高到了95分，只有一个Wrong Answer，所有的用例都在规定时间内计算完成了！居然是因为这个原因，真是无语！
于是我把代码重新调整了一下，仍然使用C标准库中的qsort对元素进行排序。但我对之前写的基于指针的二分查找不太满意，想改成基于数组索引的。于是我把《数据结构》这本书有关二分查找的章节仔细阅读了一下，并认真思考：我要怎样利用二分查找法来定位元素在数组中的位置？如果该元素并不存在于数组中，算法该返回什么？在我看来，如果元素存在于数组中，那么算法自然要返回元素在数组中的秩；如果元素不在数组中，那么算法应该返回元素插入到数组后的秩，也就是原数组中大于等于该元素的最小元素的秩。例如对于[1, 3, 7, 9, 11]，对元素6进行二分查找应该返回结果2，因为6将被插入到数组中秩为2的位置，得到[1, 3, 6, 7, 9, 11]
假设闭区间[a, b]端点都在数组中，那么对于[1, 3, 7, 9, 11]，如果要求[3, 9]中元素的个数，因为3的秩是1，9的秩是3，3-1+1 = 3，元素个数就是3。
如果闭区间[a, b]端点不都在数组中，那么就有3种情况：（1）a在b不在；（2）a不在b在；（3）a和b都不在。这3种情况下闭区间中元素个数又是多少呢？为此我构造了一些用例，进行计算并找规律：
对于数组
[1, 3, 7, 9, 11]，对于闭区间集合{[4, 6], [7, 12], [6, 6], [7, 7], [3, 11], [0, 0], [13, 13], [6, 12], [1, 13], [6, 11], [4, 11], [1, 4], [0, 7], [3, 7], [0, 13], [2, 8]}，有：
- [4, 6]：indexA = 2，indexB = 2，count = 0（a和b都不在）
- [7, 12] ：indexA = 2，indexB = 5，count = 3（a在b不在）
- [6, 6] ：indexA = 2，indexB = 2，count = 0（a和b都不在）
- [7, 7]：indexA = 2，indexB = 2，count = 1（a和b都在）
- [3, 11]：indexA = 1，indexB = 4，count = 4（a和b都在）
- [0, 0] ：indexA = 0，indexB = 0，count = 0（a和b都不在）
- [13, 13] ：indexA = 5，indexB = 5，count = 0（a和b都不在）
- [6, 12]：indexA = 2，indexB = 5，count = 3（a和b都不在）
- [1, 13]：indexA = 0，indexB = 5，count = 5（a在b不在）
- [6, 11]：indexA = 2，indexB = 4，count = 3（a不在b在）
- [4, 11]：indexA = 2，indexB = 4，count = 3（a不在b在）
- [1, 4]：indexA = 0，indexB = 2，count = 2（a在b不在）
- [0, 7]：indexA = 0，indexB = 2，count = 3（a不在b在）
- [3, 7]：indexA = 1，indexB = 2，count = 2（a和b都在）
- [0, 13] ：indexA = 0，indexB = 5，count = 5（a和b都不在）
- [2, 8]：indexA = 1，indexB = 3，count = 2（a和b都不在）
看出规律来了：
- a和b都不在：indexB - indexA
- a和b都在：indexB - indexA + 1
- a在b不在：indexB - indexA
- a不在b在：indexB - indexA + 1
再进一步归纳一下：
- 闭区间[a, b]，若b存在于数组中，则count = indexB - indexA + 1
- 闭区间[a, b]，若b不存在于数组中，则count = indexB - indexA
外加把cin/cout换成scanf/printf，以及重新采用qsort，得到如下算法：
// 算法3
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int range(int *pInt, int n, int a, int b);
int find_index_of(const int *pInt, int lo, int hi, int t);
int comp(const void *a, const void *b);
int main() {
int n, m;
scanf("%d%d", &n, &m);
int *points = new int[n];
int *answer = new int[m];
for (int i = 0; i < n; i++) {
scanf("%d", points+i);
}
qsort(points, n, sizeof(int), comp);
int a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
answer[i] = range(points, n, a, b);
}
for (int i = 0; i < m; i++) {
printf("%d\n", answer[i]);
}
delete[] points;
delete[] answer;
return 0;
}
int comp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int range(int *pInt, int n, int a, int b) {
int indexA = find_index_of(pInt, 0, n, a);
int indexB = find_index_of(pInt, 0, n, b);
int count = 0;
if (indexB < n && pInt[indexB] == b) {
count = indexB - indexA + 1;
} else if (indexB >= n || (indexB < n && pInt[indexB] != b)) {
count = indexB - indexA;
}
return count;
}
int find_index_of(const int *pInt, int lo, int hi, int t) {
while (lo < hi) {
int mi = (lo + hi) / 2;
if (t < pInt[mi])
hi = mi;
else if (pInt[mi] < t)
lo = mi + 1;
else
return mi;
}
return lo;
}
find_index_of是二分查找法基础上做了一点小小的修改。标准的二分查找法，当元素没有找到时返回-1，表示数组中不存在这个元素，这里返回的是元素待插入的位置的秩，也就是数组中大于等于元素的最小的那个元素。二分查找法看似简单，实际在编写的时候要特别注意边界值。一般来说，按照在S[lo, hi)这个左闭右开区间进行查找的方式编写，能够得到形式统一且简洁的实现，所以对于右边界而言是hi = mi，而对于左边界而言，则是lo = mi + 1，这些细节值得注意，我一开始的几个实现中就是吃了这些细节的亏，导致得到的结果并不总是正确。
上传解决方案到OJ，得到100分，完全通过！
6. 那么，该怎样解题呢？
从根本上说，要重视基础，要认真理解基本概念，复杂问题无非就是简单问题的约束性组合。有扎实的基础，再加上思维方式的训练，你就能透过复杂问题看到它背后都是由哪些基本问题通过什么方式组合在一起的。这些基本问题又能还原为哪些基本操作。
有了基础还不够，还要训练思维方式。匈牙利数学家乔治·波利亚在他的书《怎样解题：数学思维的新方法》中，介绍了解题的”内功心法“：
- 第一，你必须理解题目：
- 未知量是什么？
- 已知数据是什么？
- 条件是什么？
- 条件有可能满足吗？条件是否足以确定未知量？或者它不够充分？或者多余？或者矛盾？
- 画一张图，引入适当的符号。
- 将条件的不同部分分开。你能把它们写出来吗？
- 第二，找出已知数据与未知量之间的联系。如果找不到直接的联系，你也许不得不去考虑辅助题目。最终你应该得到一个解题方案。
- 你以前见过它吗？或者你见过同样的题目以一种稍有不同的形式出现吗？
- 你知道一道与它有关的题目吗？你知道一条可能有用的定理吗？
- 观察未知量！并尽量想出一道你所熟悉的具有相同或相似未知量的题目。
- 这里有一道题目和你的题目有关而且以前解过。你能利用它吗？你能利用它的结果吗？你能利用它的方法吗？为了有可能应用它，你是否应该引入某个辅助元素？
- 你能重新叙述这道题目吗？你还能以不同的方式叙述它吗？
- 回到定义上去。
- 如果你不能解所提的题目，先尝试去解某道有关的题目。你能否想到一道更容易着手的相关题目？一道更为普遍化的题目？一道更为特殊化的题目？一道类似的题目？你能解出这道题目的一部分吗？只保留条件的一部分，而丢掉其他部分，那么未知量可以确定到什么程度，它怎样变化？你能从已知数据中得出一些有用的东西吗？你能想到其他合适的已知数据来确定该未知量吗？你能改变未知量或已知数据，或者有必要的话，把两者都改变，从而使新的未知量和新的已知数据彼此更接近吗？你用到所有的已知数据了吗？你用到全部的条件了吗？你把题目中所有的关键概念都考虑到了吗？
- 第三，执行你的方案。
- 执行你的解题方案，检查每一个步骤。
- 你能清楚地看出这个步骤是正确的吗？
- 你能否证明它是正确的？
- 第四，检查已经得到的解答。
- 你能检验这个结果吗？
- 你能检验这个论证吗？
- 你能以不同的方式推导这个结果吗？
- 你能一眼就看出它来吗？
- 你能在别的什么题目中利用这个结果或这种方法吗？
如果能在解题的过程中有意识地使用这些问题和建议，也许就能帮助找到解决问题的思路，也就是联系已知数据和未知量的那个”桥梁“。更多的例子，请阅读这本书，它不光适用于解决数学题，还适用于解决编程题乃至其他的一些问题。
7. 辩证唯物主义的”知行合一“观
书本上的知识，读了不用，很快就会忘掉，光看书解决不了问题，还容易读成教条主义书呆子。不读书，野路子出身，仅凭经验去解决问题，容易变成经验主义的坎井之蛙。怎么看待理论和实践的关系？这个问题困扰了我很久，现在我找到答案了。那就是要统一在辩证唯物主义的知行合一观下。就是“实事求是”。
“‘实事’就是客观存在着的一切事物，‘是’就是客观事物的内部联系，即规律性，‘求’就是我们去研究。”
——毛泽东
我们在遇到一个问题的时候，要凭借良好的基础、认真的观察、仔细的思考以及调查研究将其“解压缩”成一些基本问题的有机组合，这个过程不断深入下去，不断拆解，直到问题变成几个基本知识的组合。即研究出事物内部的规律性的东西。如果中间有哪个地方卡壳了，那就说明自己的知识框架在这一部分存在漏洞，这个漏洞导致自己无法对事物产生正确的认识，那就要通过学习理论知识去补上这个漏洞，从而重新建立对客观事物的正确认识，然后再用正确的认识去指导实践。
如果连问题都看不懂，或者完全没思路，说明漏洞还有点大，这个时候就应该把问题先放一放，先带着问题去学一学理论知识，这个时候的主要矛盾是缺乏解决问题的基础知识。等基础知识掌握到一定程度了，就可以边实践边研究理论知识。等对解决一般问题驾轻就熟了，就可以不那么依靠书本而解决更多更复杂的问题了。这就好比逐步扔掉拐杖自己学会走路一样，通过实践的训练是可以做到的。
网友评论