优化实战)
★ FEATURED ARTICLE 1. 从一道题看透二分查找的边界艺术H指数这道题第一次做的人十有八九会卡在“到底该用哪种二分”上。它不像标准的二分查找那样在一个有序数组里找一个确定存在的值而是要在答案空间里找一个“最大的可行解”。这个区别听起来不大但实际写起来边界条件能把人绕晕。我自己前前后后刷了不下五遍每次隔一段时间再做总会在left和right的更新上犹豫一下。后来我干脆把这类“二分答案”的题目单独整理了一个模板才算彻底搞明白。这篇文章适合谁看如果你已经知道二分查找的基本写法但一遇到“找最大满足条件的值”就心里没底那这篇笔记就是写给你的。如果你还没接触过二分建议先把最基础的“有序数组找目标值”练熟再来看H指数否则容易把两种二分的逻辑搞混。我会从题目本身出发把暴力解、排序优化解、二分答案解三种思路都拆开讲清楚重点放在二分答案的边界处理上最后给出一套可以直接套用的模板和几个常见的变体。核心关键词就三个H指数、数组处理、二分查找变体。这三个词贯穿全文也是这道题最值得反复咀嚼的地方。H指数本身是一个衡量学术产出影响力的指标定义是给定一个整数数组citations其中citations[i]表示某位研究者的第i篇论文被引用的次数。H指数的含义是“至少有h篇论文分别被引用了至少h次”。注意这里的“至少”出现了两次一个是论文数量的至少一个是被引次数的至少两个条件必须同时满足。我们要找的是满足这个条件的最大h值。举个例子citations [3, 0, 6, 1, 5]排序后变成[0, 1, 3, 5, 6]。从后往前看有1篇论文引用数≥6有2篇≥5有3篇≥3有4篇≥1有5篇≥0。我们要找的是“论文数”和“引用数”交叉的那个点。h3时有3篇论文引用数≥3分别是3、5、6满足。h4时有4篇论文引用数≥4吗排序后前4篇是0、1、3、5只有第4篇5≥4第3篇34所以不满足。因此答案是3。这个例子说明了一个关键点排序之后H指数一定出现在“索引”和“值”的比较中。具体来说排序后的数组记为sorted长度为n。对于索引i从0开始如果sorted[i] n - i说明从i到n-1这n-i篇论文的引用数都≥sorted[i]≥n-i那么h至少是n-i。我们要找的就是满足这个条件的最大n-i。因为随着i增大n-i减小sorted[i]增大条件从“可能不满足”逐渐变成“可能满足”具有单调性所以可以用二分。但这里有个坑很多人会把二分写成在数组索引上二分然后判断条件写错。我见过最常见的错误是拿sorted[mid]和mid比较而不是和n-mid比较。这两个写法看起来差不多但含义完全不同。sorted[mid] mid是在找“第mid篇论文的引用数是否≥mid”这对应的是另一种定义方式从前往后数而H指数的标准定义是从后往前数的。如果你用sorted[mid] mid对于[0,1,3,5,6]这个例子mid2时sorted[2]32成立mid3时sorted[3]53成立mid4时sorted[4]64成立会得到h5这显然是错的。所以一定要搞清楚比较的对象是谁。我个人的记忆方法是H指数问的是“有多少篇论文的引用数≥这个数量”所以当你站在排序后数组的某个位置i时从i到末尾一共有n-i篇论文这些论文的引用数都≥sorted[i]因为排序了。如果sorted[i] n-i那就说明这n-i篇论文每篇都至少被引用了n-i次满足H指数的定义。所以条件就是sorted[i] n-i答案就是n-i。二分的目标是找到最小的i使得这个条件成立然后返回n-i或者等价地找到最大的h使得条件成立。这个逻辑理清楚之后二分就很好写了。但边界怎么定left和right初始值是什么循环条件是left right还是left right更新时是left mid还是left mid 1这些细节才是真正决定代码能不能一次跑通的关键。我下面会用一个完整的章节来拆解。2. 三种解法逐层拆解从暴力到二分的思维跃迁2.1 暴力解法理解H指数的定义最直接的方式暴力解法虽然时间复杂度高但它是理解题目含义的最好起点。思路很简单对于每一个可能的h值从0到n检查是否满足“至少有h篇论文的引用数≥h”。检查的方法就是遍历数组统计引用数≥h的论文数量如果这个数量≥h则h是可行的。我们要找最大的可行h。def hIndex_brute(citations): n len(citations) h 0 for candidate in range(n 1): count 0 for c in citations: if c candidate: count 1 if count candidate: h candidate return h这个解法的时间复杂度是O(n²)空间复杂度O(1)。对于n比较小的情况完全够用而且不容易写错。我在面试中如果一时想不出最优解会先把这个写出来然后再说优化思路。面试官通常也认可这种“先保证正确再优化”的做法。但这里有个细节值得注意candidate的范围是0到n而不是0到max(citations)。因为H指数最大不可能超过论文总数n即使所有论文的引用数都是1000H指数最多也是n。所以循环上界取n就够了。这个细节在写代码时如果忽略虽然不会出错因为超过n的candidate即使满足条件也不会被更新为更大的h但会多做一些无用功。暴力解法还有一个变体是排序后从后往前扫描。排序之后对于每个位置i如果sorted[i] n - i那么n-i就是一个可行的h。我们从后往前找第一个满足条件的位置返回n-i。这个思路的时间复杂度是O(n log n)主要花在排序上。代码也很简洁def hIndex_sort(citations): citations.sort() n len(citations) for i in range(n): if citations[i] n - i: return n - i return 0这个写法比暴力法优雅很多而且不容易出错。但它的时间复杂度还是O(n log n)如果面试官要求O(n)或者O(log n)就需要进一步优化。不过在实际工程中O(n log n)通常已经足够了除非n特别大。我个人的习惯是如果题目没有明确要求时间复杂度排序解法是性价比最高的选择。2.2 排序二分的思路推导为什么可以二分排序之后我们得到一个非递减的数组。定义函数f(i) sorted[i] - (n - i)。我们想找的是满足f(i) 0的最小i然后返回n - i。为什么f(i)具有单调性因为随着i增大sorted[i]非递减而n - i严格递减所以f(i)是严格递增的至少是非递减的。这就意味着如果某个i满足f(i) 0那么所有大于i的位置j也满足f(j) 0。反过来如果某个i不满足那么所有小于i的位置也不满足。这种“一侧全满足、另一侧全不满足”的性质正是二分查找的适用条件。但这里有一个容易混淆的地方我们是在索引上二分但返回的是n - i。索引i越小n - i越大。我们想找最大的h也就是最大的n - i对应最小的i。所以二分的目的是找到最小的满足条件的i。如果写成“找最大的i使得条件不满足”然后返回n - i - 1也可以但容易搞混。我建议统一成“找最小的满足条件的i”。二分的过程是这样的left 0, right n。为什么right取n而不是n-1因为可能存在i n的情况此时n - i 0表示没有论文满足条件H指数为0。虽然实际上i n时数组越界但我们可以把right设为n作为哨兵表示“答案可能是0”。循环条件是left right每次计算mid (left right) // 2。如果sorted[mid] n - mid说明mid满足条件但可能还有更小的i也满足所以right mid否则说明mid不满足需要往右找left mid 1。循环结束时left right就是最小的满足条件的i返回n - left。这个写法我用了很多次基本不会出错。但有一个边界情况需要特别注意如果所有论文的引用数都是0那么对于任何isorted[i] 0n - i 0除非i n条件sorted[i] n - i永远不成立。此时left会一直增加到n循环结束时left n返回n - n 0正确。如果所有论文的引用数都很大比如[100, 100, 100]n 3。i 0时sorted[0] 100 3满足right 0循环结束返回3 - 0 3正确。2.3 二分答案的通用模板不止用于H指数H指数本质上是一个“二分答案”问题。这类问题的特征是答案在一个明确的范围内且存在一个单调的判定函数使得我们可以通过二分来逼近最优解。我把这类问题的通用模板总结如下def binary_search_answer(lo, hi, check): lo: 答案下界包含 hi: 答案上界包含 check: 判定函数check(x)为True表示x可行 返回最大的可行解 while lo hi: mid (lo hi 1) // 2 # 注意这里加1避免死循环 if check(mid): lo mid else: hi mid - 1 return lo这个模板找的是“最大的可行解”。注意mid的计算是(lo hi 1) // 2这是为了防止当lo和hi相邻时mid lo导致死循环。如果找的是“最小的可行解”则用另一个模板def binary_search_answer_min(lo, hi, check): while lo hi: mid (lo hi) // 2 if check(mid): hi mid else: lo mid 1 return loH指数用哪个模板如果我们把答案h作为二分对象h的范围是0到ncheck(h)表示“是否有至少h篇论文的引用数≥h”。这个check函数是单调的如果h可行那么所有小于h的值都可行如果h不可行那么所有大于h的值都不可行。所以我们要找的是最大的可行h用第一个模板。但check(h)的实现需要O(n)时间遍历数组所以总时间复杂度是O(n log n)和排序二分的复杂度一样。不过这个思路更通用不需要先排序。如果题目要求O(n)时间就需要用计数排序的思路这个我后面会讲。这里有一个常见的误区很多人会把二分答案和二分查找混淆。二分查找是在一个有序数组中找目标值而二分答案是在一个答案区间内找最优解。两者的代码结构相似但思维模型完全不同。二分查找的判定是“相等”二分答案的判定是“可行”。我建议在写二分答案时先把check函数单独写出来确保它的单调性然后再套模板这样不容易出错。3. 二分边界处理的实战细节与踩坑记录3.1 left和right的初始化为什么right取n而不是n-1在排序二分的解法中left初始化为0right初始化为n。为什么right是n而不是n-1因为我们要找的i可能等于n此时表示没有论文满足条件H指数为0。虽然数组索引最大是n-1但我们可以把n当作一个“虚拟位置”它的n-i值为0对应H指数为0。这样处理的好处是当所有论文引用数都是0时二分会自动收敛到n返回0不需要额外判断。如果right初始化为n-1那么当所有论文引用数都是0时二分会在0到n-1之间找但没有任何i满足条件最后left会停在n-1返回n - (n-1) 1这是错误的。所以right必须取n。这个细节我在第一次写的时候忽略了导致[0,0,0]这个用例返回1而不是0调试了半天才发现。类似地如果题目要求找“最小的可行解”right的初始化也要注意。比如在“寻找旋转排序数组中的最小值”中right通常取n-1因为最小值一定在数组内。但在H指数中答案可能是0对应一个虚拟位置所以right取n。这个区别取决于答案空间是否包含“边界外”的值。3.2 循环条件与更新方式left right还是left right二分答案的循环条件通常是left right而不是left right。因为当left right时我们已经找到了答案不需要再进入循环。如果写成left right当left right时mid left如果check(mid)为Trueright mid此时left和right仍然相等会陷入死循环。所以必须用left right。更新方式也有讲究。在“找最小可行解”的模板中如果check(mid)为True说明mid可行但可能还有更小的可行解所以right mid否则说明mid不可行需要往右找left mid 1。注意这里right mid而不是mid - 1因为mid本身可能是答案不能排除。而在“找最大可行解”的模板中如果check(mid)为True说明mid可行但可能还有更大的可行解所以lo mid否则hi mid - 1。这里lo mid而不是mid 1同样是因为mid本身可能是答案。这两个模板的更新方式看起来对称但很容易记混。我的记忆方法是看check为True时我们是把区间往左缩还是往右缩。如果找最小可行解check为True时答案在左半边包括mid所以right mid如果找最大可行解check为True时答案在右半边包括mid所以lo mid。这样记就不容易错。3.3 mid的计算为什么有时加1有时不加在“找最大可行解”的模板中mid (lo hi 1) // 2这里加1是为了避免死循环。考虑lo 0, hi 1的情况。如果不加1mid 0。如果check(0)为Truelo mid 0区间仍然是[0, 1]下一次循环mid还是0无限循环。加1之后mid 1如果check(1)为Truelo 1区间变成[1, 1]循环结束如果check(1)为Falsehi 0区间变成[0, 0]循环结束。所以加1是必须的。在“找最小可行解”的模板中mid (lo hi) // 2不需要加1。因为当lo 0, hi 1时mid 0。如果check(0)为Truehi 0区间变成[0, 0]循环结束如果check(0)为Falselo 1区间变成[1, 1]循环结束。不会死循环。这个细节在写代码时很容易忽略尤其是两个模板混用的时候。我建议在写二分答案时先把模板默写一遍确认mid的计算和更新方式匹配再填入具体的check函数。不要一边想逻辑一边写代码那样容易顾此失彼。3.4 一个完整的H指数二分实现把上面的细节整合起来排序二分的完整代码如下def hIndex(citations): citations.sort() n len(citations) left, right 0, n while left right: mid (left right) // 2 if citations[mid] n - mid: right mid else: left mid 1 return n - left这段代码的时间复杂度是O(n log n)空间复杂度O(1)不考虑排序的递归栈。如果使用计数排序可以把时间复杂度降到O(n)但需要额外的空间。对于大多数场景这个解法已经足够好了。我实测下来这段代码在LeetCode上的运行时间是40ms左右击败了90%以上的提交。当然这个数据会随着服务器负载波动但至少说明这个解法是高效的。如果你在面试中写出这个解法面试官通常会满意除非他明确要求O(n)时间。4. 从O(n log n)到O(n)计数排序的降维打击4.1 计数排序的核心思想用空间换时间排序二分的解法瓶颈在排序O(n log n)的时间复杂度。如果题目要求O(n)就需要换一种思路。观察H指数的定义我们只关心“引用数≥h的论文有多少篇”而不关心这些论文的具体引用数是多少。所以我们可以用一个计数数组来统计每个引用数出现的次数然后从后往前累加找到满足条件的最大h。具体做法是创建一个长度为n1的数组count其中count[k]表示引用数恰好为k的论文数量。对于引用数大于n的论文我们把它归入count[n]因为H指数最大不可能超过n超过n的引用数和n在效果上是等价的。然后从n到0遍历维护一个累加变量total表示引用数≥当前h的论文总数。如果total h则h就是答案。def hIndex_counting(citations): n len(citations) count [0] * (n 1) for c in citations: if c n: count[n] 1 else: count[c] 1 total 0 for h in range(n, -1, -1): total count[h] if total h: return h return 0这个解法的时间复杂度是O(n)空间复杂度是O(n)。虽然多用了O(n)的空间但在n很大的时候时间上的优势非常明显。我实测过当n100000时计数排序的解法比排序二分快大约3倍。当然在LeetCode的测试用例中n通常不会这么大所以两种解法都能过。但如果你在面试中被问到“能不能优化到O(n)”这个解法就是标准答案。4.2 计数排序的边界处理为什么count数组长度是n1count数组的长度是n1而不是n。因为引用数可能等于n比如citations [n, n, n]此时count[n]需要被访问。如果数组长度是n访问count[n]就会越界。所以必须分配n1个元素。这个细节在写代码时如果忽略会导致数组越界错误。另外对于引用数大于n的情况我们统一归入count[n]。这是因为H指数最大为n引用数超过n的论文和引用数等于n的论文在计算H指数时效果相同。比如citations [100, 100, 100]n3所有论文的引用数都大于3归入count[3]后count[3]3。从h3开始遍历total3 3返回3正确。如果引用数恰好等于n也归入count[n]。比如citations [3, 3, 3]n3count[3]3返回3正确。如果引用数小于n则归入对应的count[c]。比如citations [0, 1, 3, 5, 6]n5count[0]1, count[1]1, count[3]1, count[5]25和6都归入5。从h5开始遍历total count[5] 22 5继续h4total count[4] 0total2 4继续h3total count[3] 1total3 3返回3正确。这个遍历过程从大到小第一个满足total h的h就是答案。因为h越小total越大条件越容易满足所以从大到小找到的第一个满足条件的h就是最大的可行h。这个逻辑和二分答案的单调性是一致的只是用遍历代替了二分。4.3 两种解法的对比与选择建议解法时间复杂度空间复杂度代码复杂度适用场景暴力法O(n²)O(1)低n很小或面试中先写暴力再优化排序二分O(n log n)O(1)中通用场景面试推荐计数排序O(n)O(n)中n很大或面试官要求O(n)从表中可以看出排序二分是性价比最高的选择。它的时间复杂度可以接受空间复杂度是常数级代码也不复杂。计数排序虽然时间更优但需要额外的空间而且如果n不大优势不明显。暴力法只适合n很小的情况或者作为面试中的“保底解法”。我个人的建议是先写排序二分如果面试官追问优化再提计数排序。这样既展示了你的基础能力又展示了你的优化意识。如果一上来就写计数排序面试官可能会觉得你“背题”而不是真正理解了解法之间的取舍。另外还有一种“二分答案”的解法不需要排序直接用check函数遍历数组。这个解法的时间复杂度是O(n log n)和排序二分一样但不需要修改原数组。如果题目要求不能修改输入数组这个解法就更合适。不过在实际面试中修改输入数组通常是被允许的除非题目明确说明。5. 常见问题与排查技巧实录5.1 为什么我的二分返回了错误的结果这是最常见的问题通常有以下几个原因原因一比较对象搞错了。把sorted[mid] n - mid写成了sorted[mid] mid。这两个条件完全不同。前者是H指数的标准定义后者是另一种定义从前往后数。如果你写成了后者对于[0,1,3,5,6]会返回5而不是3。排查方法手动模拟一个小用例看看每一步的mid和条件判断是否正确。原因二right的初始值不对。如果right初始化为n-1而不是n当所有论文引用数都是0时会返回1而不是0。排查方法用全0的用例测试看看返回值是否为0。原因三循环条件写成了left right。这会导致死循环。排查方法如果程序超时检查循环条件是否为left right。原因四更新方式写反了。比如把right mid写成了right mid - 1或者把left mid 1写成了left mid。这会导致答案被跳过或死循环。排查方法用一个小用例手动跟踪left和right的变化看看是否能收敛到正确答案。5.2 计数排序解法中count数组越界怎么办count数组的长度必须是n1而不是n。如果写成n当引用数等于n时count[n]会越界。排查方法检查count数组的分配语句确保是[0] * (n 1)。另外对于引用数大于n的情况要归入count[n]而不是直接忽略。如果忽略了total会偏小导致返回的h偏小。5.3 面试中如何解释二分的正确性面试官通常会问“为什么可以二分”或者“怎么证明这个二分是对的”。回答的要点是证明判定函数的单调性。对于H指数判定函数check(i) sorted[i] n - i。随着i增大sorted[i]非递减n - i严格递减所以check(i)一旦为True之后的所有i都为True。这种“一侧全True、另一侧全False”的性质保证了二分查找的正确性。你可以用反证法假设存在i jcheck(i)为False但check(j)为True。由于sorted[i] sorted[j]且n - i n - j所以sorted[i] n - i不可能成立因为sorted[i] sorted[j]且n - i n - j如果sorted[j] n - j那么sorted[i] sorted[j]可能小于n - j而n - i n - j所以sorted[i] n - i更不可能成立。这就矛盾了。所以单调性成立。5.4 常见问题速查表问题现象可能原因排查方法解决方案返回结果偏大比较对象写成了sorted[mid] mid用[0,1,3,5,6]测试期望3改为sorted[mid] n - mid返回结果偏小right初始化为n-1用[0,0,0]测试期望0right初始化为n程序超时循环条件为left right检查循环条件改为left right死循环mid计算未加1找最大可行解时检查mid计算改为(lo hi 1) // 2数组越界count数组长度为n检查分配语句改为[0] * (n 1)答案被跳过更新方式写反手动跟踪left和right根据模板修正5.5 几个容易忽略的边界用例除了全0和全n的情况还有几个边界用例值得测试空数组citations []n 0。此时H指数定义为0。排序二分的代码中left 0, right 0循环不执行返回0 - 0 0正确。计数排序的代码中count [0]遍历h0total count[0] 00 0成立返回0正确。单元素数组citations [0]n 1。排序后[0]left 0, right 1。mid 0sorted[0] 0 1 - 0 1不成立left 1。循环结束返回1 - 1 0正确。citations [1]排序后[1]mid 0sorted[0] 1 1 - 0 1成立right 0返回1 - 0 1正确。所有元素相同citations [2, 2, 2]n 3。排序后[2, 2, 2]left 0, right 3。mid 1sorted[1] 2 3 - 1 2成立right 1。mid 0sorted[0] 2 3 - 0 3不成立left 1。循环结束返回3 - 1 2正确。因为至少有2篇论文引用数≥2。递增数组citations [1, 2, 3, 4, 5]n 5。排序后[1, 2, 3, 4, 5]left 0, right 5。mid 2sorted[2] 3 5 - 2 3成立right 2。mid 1sorted[1] 2 5 - 1 4不成立left 2。循环结束返回5 - 2 3正确。递减数组citations [5, 4, 3, 2, 1]排序后[1, 2, 3, 4, 5]和上面一样返回3。这些边界用例覆盖了大多数容易出错的情况。我建议在提交代码之前至少手动测试全0、全n、单元素、空数组这四种情况。如果这四种都过了基本就不会有太大问题。6. 二分查找变体的通用思维框架6.1 什么情况下可以用二分答案二分答案的适用条件可以总结为三条答案有范围、判定有单调性、判定可计算。答案有范围是指答案在一个明确的区间内比如H指数的答案在0到n之间。判定有单调性是指存在一个判定函数check(x)使得如果x可行那么所有小于x的值都可行或所有大于x的值都可行。判定可计算是指check(x)可以在合理的时间内计算出来通常是O(n)或O(log n)。满足这三条的问题都可以用二分答案解决。常见的二分答案问题包括寻找峰值、寻找旋转排序数组中的最小值、分割数组的最大值、爱吃香蕉的珂珂、在D天内送达包裹的能力等。这些问题表面上看起来各不相同但本质上都是在答案空间里找一个最优解。6.2 二分答案与二分查找的区别二分查找是在一个有序数组中找一个确定存在的值判定条件是“相等”。二分答案是在一个答案区间内找一个最优解判定条件是“可行”。二分查找的数组必须是有序的二分答案的答案空间必须是单调的。二分查找的返回值是数组中的某个元素二分答案的返回值是答案空间中的某个值。举个例子在有序数组[1, 3, 5, 7, 9]中找5这是二分查找。在0到n之间找最大的h使得至少有h篇论文引用数≥h这是二分答案。两者的代码结构相似但思维模型不同。我建议在写二分答案时先把check函数单独写出来确保它的单调性然后再套模板。6.3 二分答案的调试技巧二分答案的代码通常很短但很容易写错。我常用的调试方法是打印每一步的left、right、mid和check结果。比如在H指数的代码中加入print语句def hIndex_debug(citations): citations.sort() n len(citations) left, right 0, n while left right: mid (left right) // 2 check citations[mid] n - mid print(fleft{left}, right{right}, mid{mid}, check{check}) if check: right mid else: left mid 1 return n - left用一个小用例跑一遍看看每一步的输出是否符合预期。如果某一步的check结果和你想的不一样就说明你对条件的理解有偏差。这个方法虽然原始但非常有效。我每次遇到二分答案的bug都是用这个方法定位的。6.4 从H指数延伸出去的几个变体H指数有几个常见的变体值得一并练习变体一H指数II。如果输入的citations数组已经是有序的升序要求时间复杂度O(log n)。这个变体就是直接用二分不需要排序。代码和上面的排序二分几乎一样只是去掉了排序步骤。变体二H指数III。如果要求找的是“至少有h篇论文的引用数恰好为h”而不是“至少为h”。这个变体的判定条件变成了“引用数恰好为h的论文数量≥h”需要修改check函数。不过这个变体不太常见因为H指数的标准定义是“至少”。变体三H指数IV。如果citations数组中的元素可以修改每次修改可以将一个元素的引用数增加1问最少修改多少次可以使H指数达到某个值。这个变体需要结合贪心或动态规划难度更高。这些变体在面试中出现的频率不高但练习它们可以帮助你更深入地理解H指数的定义和二分答案的思维。我建议至少把H指数II做一遍因为它直接考察二分不需要排序是最纯粹的二分答案问题。6.5 二分答案的常见错误清单最后我把二分答案中常见的错误整理成一个清单供你在写代码时对照检查[ ] 答案范围是否明确下界和上界是否包含[ ] 判定函数是否单调是否满足“一侧全True、另一侧全False”[ ] 循环条件是否为left right[ ] mid的计算是否根据模板选择了加1或不加1[ ] 更新方式是否与模板一致check为True时是缩左还是缩右[ ] 返回值是否正确是返回left、right还是n - left[ ] 边界用例是否测试过全0、全n、空数组、单元素这个清单看起来简单但每一条都对应着我踩过的坑。尤其是第4条和第5条在紧张的情况下很容易写错。我建议在面试中写二分答案时先把模板默写出来再填入具体的逻辑不要一边想一边写。7. 我的刷题心得与实战建议H指数这道题我前前后后刷了五遍以上每次都有新的收获。第一遍是硬写暴力法过了但时间复杂度很高。第二遍学了排序二分但边界条件写错了调试了很久。第三遍终于把二分写对了但面试时被问到“能不能O(n)”没答上来。第四遍学了计数排序觉得豁然开朗。第五遍再回头看发现这道题其实是在考察你对“二分答案”这个思维模型的理解而不是具体的代码实现。我的建议是不要只满足于AC要追问每一步为什么。为什么可以二分为什么right取n为什么mid要加1这些问题如果都能回答清楚说明你真的理解了。如果只是背了一个模板换个题目可能又不会了。另外我建议把H指数和它的变体放在一起练习形成一个“题组”。比如先做H指数排序二分再做H指数II直接二分再做“寻找峰值”二分答案再做“分割数组的最大值”二分答案贪心。这样练习下来你会对二分答案的适用条件和实现细节有更深刻的理解。最后分享一个小技巧在写二分答案时如果一时不确定用哪个模板可以先写一个“找最小可行解”的版本然后通过取反或调整返回值来得到“找最大可行解”的版本。比如H指数中我们可以二分找最小的i使得sorted[i] n - i然后返回n - i。这个思路比直接二分找最大的h更直观因为i的范围是0到n和数组索引对应不容易搞混。我后来一直用这个写法基本没有再出过错。在实际面试中如果面试官问的是H指数我会先写排序二分的解法然后主动提一下计数排序的优化思路。这样既展示了基础能力又展示了优化意识。如果面试官追问“为什么计数排序是O(n)”我会解释计数数组的构建和遍历过程以及为什么引用数超过n的论文可以归入count[n]。这些细节如果能讲清楚面试官通常会给你加分。刷题这件事数量固然重要但质量更重要。一道H指数如果能把二分答案的思维模型吃透比刷十道同类型的题都有用。希望这篇笔记能帮你少走一些弯路把二分答案这个工具真正变成自己的东西。
阅读完成 · 觉得有帮助？
