企业官网建设流程全解析

1. 从两道题看"查找"这件事的本质差异

"找出数组中重复的数"和"二维数组中的查找"，这两道题放在一起看特别有意思。它们表面上都是"在一个数据结构里找某个东西"，但底层思路完全是两条路。前者考察的是空间换时间的取舍，后者考察的是利用数据有序性逐步缩小搜索范围的能力。很多人刷题的时候把它们当成两个孤立的知识点背下来，结果面试稍微变个形就懵了。我自己在带新人的过程中发现，真正理解这两道题的人，后面遇到"找缺失的数""找出现奇数次的数""有序矩阵中第K小"这类变体时，基本都能自己推出来。

这篇文章我会把这两道题拆到骨头里。不只是给代码，而是把每一步为什么这么设计、我当时踩过哪些坑、面试官喜欢追问什么方向，全部摊开讲。适合正在准备技术面试的朋友，也适合已经工作但想重新梳理算法基础的人。你不需要有很强的数学背景，只要会写基本的循环和条件判断就能跟上。

先说清楚这两道题各自在问什么。"找出数组中重复的数"通常的设定是：一个长度为 n+1 的数组，里面所有数字都在 1 到 n 的范围内，也就是说至少有一个数字是重复的，要求找出任意一个重复的数字。而"二维数组中的查找"的典型设定是：一个矩阵，每一行从左到右递增，每一列从上到下递增，给一个目标值，判断它是否在矩阵中。两个问题的输入结构不同，但核心都在问同一件事——你能否利用数据的性质，避免暴力遍历所有元素。

2. "找出数组中重复的数"的四种解法与选型逻辑

2.1 暴力双重循环：能跑通但面试官不会满意

最直觉的做法是两层循环，外层遍历每个元素，内层检查它后面有没有相同的值。时间复杂度 O(n²)，空间复杂度 O(1)。代码写起来大概是这样：

def find_duplicate_brute(nums): n = len(nums) for i in range(n): for j in range(i + 1, n): if nums[i] == nums[j]: return nums[i] return -1

这段代码逻辑没问题，但面试中如果只给出这个方案，基本就到此为止了。原因很简单：当 n 是十万级别的时候，O(n²) 的耗时是不可接受的。不过我要说一个很多人忽略的点——在某些受限环境下，暴力法反而是唯一可行的方案。比如你面对的是一个只读的、不能修改的数组，而且额外空间被严格限制到 O(1)，同时数据规模很小，那暴力法就是合理选择。所以不要一上来就否定它，而是要学会说"在什么条件下我会选它"。

2.2 哈希表法：最直观的空间换时间

用一个集合或者哈希表来记录已经见过的数字，遍历数组时如果当前数字已经在集合里，就说明找到了重复的数。

def find_duplicate_hash(nums): seen = set() for num in nums: if num in seen: return num seen.add(num) return -1

时间复杂度 O(n)，空间复杂度 O(n)。这是大多数人第一反应能想到的最优解。它的优点是逻辑极其清晰，不容易写错，而且这个思路可以直接迁移到"找出所有重复的数""找出第一个重复的数"等变体上。缺点是额外开了一个集合，如果面试官追问"能不能把空间降到 O(1)"，你就需要换方案了。

这里有个实操细节值得注意：在 Python 里用set做成员判断的平均时间复杂度是 O(1)，但这是在哈希函数分布均匀的前提下。如果你用的是自定义对象或者哈希冲突严重的场景，实际性能会打折扣。不过对于整数数组来说，这个担心是多余的。

2.3 原地交换法：利用"数字范围在1到n"这个条件

这道题有一个非常关键的条件——所有数字都在 1 到 n 的范围内。这意味着如果数组中没有重复，那么排序后每个位置 i 上的数字应该是 i+1。利用这个性质，我们可以把每个数字"归位"：把数字 num 放到下标 num-1 的位置上。如果在归位过程中发现目标位置已经有了相同的数字，那就找到了重复。

def find_duplicate_swap(nums): i = 0 while i < len(nums): if nums[i] == i + 1: i += 1 continue target_idx = nums[i] - 1 if nums[target_idx] == nums[i]: return nums[i] nums[i], nums[target_idx] = nums[target_idx], nums[i] return -1

时间复杂度 O(n)，空间复杂度 O(1)。这个解法的精妙之处在于它把数组本身当成了哈希表来用——下标就是 key，元素值就是 value。每次交换都至少让一个数字回到正确位置，所以总的交换次数不超过 n 次，整体是线性的。

但我要提醒一个坑：这个解法会修改原数组。如果题目要求不能修改输入数组，这个方案就不能用。我在实际面试中就遇到过面试官先让你写这个解法，然后追问"如果数组是只读的呢"，这时候就需要换思路了。

2.4 二分答案法：不修改数组的 O(n log n) 方案

如果数组只读且要求 O(1) 空间，可以用二分法在"数值范围"上做文章。思路是：对于数值区间 [1, n]，取中点 mid，统计数组中值在 [1, mid] 范围内的元素个数。如果这个个数大于 mid，说明重复的数一定在 [1, mid] 中；否则在 [mid+1, n] 中。

def find_duplicate_binary(nums): lo, hi = 1, len(nums) - 1 while lo < hi: mid = (lo + hi) // 2 count = sum(1 for num in nums if lo <= num <= mid) if count > mid - lo + 1: hi = mid else: lo = mid + 1 return lo

时间复杂度 O(n log n)，空间复杂度 O(1)。这个方案的好处是不修改原数组，缺点是比前面的方案慢一些。它的核心思想是抽屉原理：如果 5 个苹果放进 4 个抽屉，必然有一个抽屉里至少有两个苹果。这个思路在很多"找重复/找缺失"的题目中都能复用。

2.5 四种方案的选型对照

面试中的策略是：先说出哈希表法（展示你能快速给出可行解），然后主动提"如果要求空间 O(1) 且可以修改数组，可以用原地交换；如果数组只读，可以用二分答案"。这样一次性展示了你对多个方案的理解和取舍能力，比只写一个最优解效果更好。

3. "二维数组中的查找"为什么从右上角出发

3.1 暴力遍历和逐行二分的局限

二维数组查找的题目设定是：矩阵的每一行从左到右递增，每一列从上到下递增。最直接的做法是遍历整个矩阵，O(m×n) 的时间复杂度。稍微好一点的做法是对每一行做二分查找，时间复杂度 O(m log n)。但这两个方案都没有充分利用"列也是有序的"这个条件。

我第一次做这道题的时候，想的是"能不能先确定目标值大概在哪几行"，于是对第一列做二分找到行范围，再在每行里做二分。这个思路方向是对的，但实现起来比较绕，而且最坏情况下仍然是 O(m log n)。后来看到从右上角出发的解法，才意识到这道题的精髓在于每一步都能排除一整行或一整列。

3.2 右上角出发的排除逻辑

从矩阵的右上角开始比较。设当前位置为 (row, col)，初始时 row=0，col=n-1。比较 matrix[row][col] 和目标值 target：

• 如果 matrix[row][col] == target，找到了，返回 true。
• 如果 matrix[row][col] > target，因为当前列从上到下递增，当前元素是这一列最小的（在 row 以上的行已经被排除了），所以这一列的所有元素都大于 target，可以排除整列，col 减一。
• 如果 matrix[row][col] < target，因为当前行从左到右递增，当前元素是这一行最大的（在 col 以右的列已经被排除了），所以这一行的所有元素都小于 target，可以排除整行，row 加一。

def search_matrix(matrix, target): if not matrix or not matrix[0]: return False rows, cols = len(matrix), len(matrix[0]) row, col = 0, cols - 1 while row < rows and col >= 0: if matrix[row][col] == target: return True elif matrix[row][col] > target: col -= 1 else: row += 1 return False

时间复杂度 O(m+n)，因为每次要么 row 加一要么 col 减一，最多走 m+n 步。空间复杂度 O(1)。

3.3 为什么左下角也可以，但左上角和右下角不行

这个问题的关键洞察是：起点必须满足"在一个方向上增大、在另一个方向上减小"的性质。右上角往左变小、往下变大，所以可以根据比较结果明确排除一个方向。左下角同理，往上变小、往右变大，也可以。

但左上角往右变大、往下也变大，当你发现当前值小于 target 时，你无法确定是该往右还是往下，两个方向都有可能。右下角往左变小、往上也变小，同样无法做出明确决策。所以只有右上角和左下角这两个"鞍点"位置适合作为起点。

我在面试中遇到过面试官追问"如果矩阵不是每行每列都递增，而是每行递增但列之间没有关系呢"，这时候右上角出发的解法就失效了，需要退回到逐行二分的方案。所以理解解法的适用前提比记住解法本身更重要。

3.4 一个容易写错的边界条件

很多人写这个算法时，循环条件写成row < rows and col >= 0，这个是对的。但有一种常见错误是写成row <= rows，这会导致数组越界。另外，当矩阵为空或者矩阵的第一行为空时，需要提前返回 false，否则matrix[0]会报错。这些边界条件看起来简单，但在面试手写代码时特别容易漏掉。

4. 两道题背后的通用思维模型

4.1 "利用数据性质"比"套模板"更重要

这两道题放在一起，最核心的启示是：解题的关键不在于你记住了多少模板，而在于你能否识别出数据本身的特殊性质，并利用这些性质来缩小搜索空间。

"找出数组中重复的数"利用了"数字范围在 1 到 n"这个性质，才能做到原地交换或二分答案。"二维数组中的查找"利用了"行有序且列有序"这个性质，才能做到 O(m+n)。如果把二维数组的行列有序条件去掉，这道题就退化成了普通的矩阵搜索，只能暴力遍历。

我见过很多人在刷题时喜欢按标签分类——"这是哈希表的题""这是二分的题"——然后套对应的模板。这种做法在简单题上有效，但遇到变形题就容易卡住。更好的习惯是：拿到题目先问自己"输入数据有什么特殊性质？这些性质能帮我排除哪些可能性？"

4.2 从"找重复"到"找缺失"的思路迁移

"找出数组中重复的数"的原地交换思路，可以直接迁移到"找出 1 到 n 中缺失的数"。比如一个长度为 n 的数组，数字范围是 1 到 n+1，有一个数缺失了，要求找出来。用类似的归位思路，把每个数字放到它应该在的位置上，最后检查哪个位置上的数字不对，就能找到缺失的数。

二分答案的思路也可以迁移。比如"找出有序数组中缺失的第 k 个数"，就是在数值范围上做二分，统计某个范围内实际有多少个元素，和理论值比较，决定往哪边收缩。这类题的核心都是抽屉原理 + 二分。

4.3 从"二维查找"到"有序矩阵第K小"的延伸

二维数组查找的排除思路，在"有序矩阵中第 K 小的元素"这道题中也有体现。那道题可以用最小堆做多路归并，也可以用二分答案在数值范围上搜索。二分答案的做法是：取一个中间值 mid，统计矩阵中小于等于 mid 的元素个数，如果个数小于 K 就增大下界，否则减小上界。统计个数时，利用每行有序的性质，从每行的右上角开始往左数，整体是 O(m+n) 的。

你会发现，右上角出发的排除逻辑在这里又出现了。这就是我说的"通用思维模型"——一旦你真正理解了一个解法的底层逻辑，它会在很多看似不同的问题中反复出现。

5. 面试现场怎么写才不慌

5.1 先沟通再动手，别上来就写代码

我刚开始面试的时候，拿到题目就急着写代码，结果写到一半发现思路有问题，擦掉重来，时间浪费了不说，还给面试官留下了"思维不清晰"的印象。后来我养成了一个习惯：拿到题目先用两三句话复述问题，确认自己理解无误，然后说出至少一个可行解法的思路，再问面试官"我可以开始写了吗"。

这个沟通环节看起来是在"浪费时间"，实际上是在降低后续返工的概率。而且面试官往往会在你描述思路的时候给出提示，比如"你这个方案的空间复杂度能优化吗"，这相当于免费获得了方向指引。

5.2 边界条件在写代码之前就想清楚

两道题都有一些容易忽略的边界条件：

• 数组为空或只有一个元素时怎么处理？
• 矩阵为空、只有一行、只有一列时怎么处理？
• 目标值比矩阵中所有元素都小或都大时怎么处理？
• 数组中所有元素都相同的情况下，原地交换法会不会死循环？

我的做法是在写代码之前，先在草稿纸上列出三到五个测试用例，包括正常情况和边界情况。写完代码后，用这些用例逐个走一遍。这个习惯帮我避免了很多"代码逻辑对但边界没处理"的失分。

5.3 主动说出时间空间复杂度

写完代码后，不要等面试官问，主动说出时间复杂度和空间复杂度，并解释是怎么算出来的。比如原地交换法，你可以说"每次交换至少让一个数字归位，所以总交换次数不超过 n 次，循环中 i 虽然有时不前进，但整体均摊下来是 O(n)"。这种解释展示的是你的分析能力，比单纯报一个数字更有说服力。

5.4 被追问时的应对策略

面试官常见的追问方向有几个：

• "如果数组中有多个重复的数，你要找出所有重复的数怎么办？"——哈希表法可以直接扩展，原地交换法需要调整。
• "如果要求空间复杂度严格 O(1) 且不能修改数组呢？"——二分答案法。
• "如果二维矩阵的行列有序条件只满足一个呢？"——退化为逐行二分或逐列二分。
• "你的算法在最坏情况下的表现如何？"——需要具体分析，比如哈希表在极端哈希冲突下的退化。

遇到追问不要慌，先确认自己理解了问题，然后基于已有的解法做调整。如果一时想不到最优解，可以先说出一个可行的次优解，再逐步优化。面试官更看重的是你的思考过程，而不是你能不能秒出最优解。

6. 我踩过的几个真实坑

6.1 原地交换法中的死循环

我第一次写原地交换法的时候，代码是这样的：

def find_duplicate_buggy(nums): for i in range(len(nums)): while nums[i] != i + 1: target_idx = nums[i] - 1 if nums[target_idx] == nums[i]: return nums[i] nums[i], nums[target_idx] = nums[target_idx], nums[i] return -1

看起来没问题对吧？但如果数组中有重复的数，而且重复的数恰好已经在正确位置上，这个循环就会卡住。比如[2, 2, 1]，i=0 时 nums[0]=2，target_idx=1，nums[1]=2，发现重复，返回 2，这个没问题。但如果是[1, 1]，i=0 时 nums[0]=1 已经归位，i=1 时 nums[1]=1，target_idx=0，nums[0]=1，发现重复，返回 1，也没问题。

真正会出问题的是当nums[i]的值不在 1 到 n 范围内时，target_idx可能越界。虽然题目通常保证了范围，但如果你在面试中不主动确认这个条件，写出来的代码就可能存在隐患。我的建议是：在代码开头加一个范围检查，或者在注释中明确说明"假设所有数字都在 1 到 n 范围内"。

6.2 二维查找中行列索引的混淆

二维数组查找中，row 和 col 的更新方向特别容易搞混。我有一次面试时把"当前值大于目标值就 col 减一"写成了"row 减一"，结果整个逻辑就崩了。后来我总结了一个记忆方法：右上角的元素，往左走是变小，往下走是变大。所以当前值比目标大，说明需要变小，往左走，col 减一；当前值比目标小，说明需要变大，往下走，row 加一。

这个记忆方法看起来简单，但在紧张的手写代码环境下，能帮你快速确认方向对不对。

6.3 忽略"数组只读"这个约束

有一次面试，我先写了原地交换法，面试官说"如果这个数组是只读的呢"。我当时第一反应是"那就用哈希表"，但面试官追问"能不能不用额外空间"。我卡了一下才想到二分答案法。这个经历让我意识到，在给出解法之前，应该主动询问或确认题目的约束条件——数组是否可修改、额外空间是否有限制、数据范围是什么。这些信息直接决定了你应该选哪个方案。

6.4 二分答案法中 count 的统计范围写错

二分答案法的核心是统计[lo, mid]范围内元素的个数。我一开始写成了统计[1, mid]的个数，导致 lo 不是 1 的时候结果出错。正确的做法是统计当前搜索区间[lo, mid]内的元素个数，然后和mid - lo + 1比较。这个细节在面试中很容易被忽略，但一旦写错，整个二分的方向就错了。

7. 从这两道题延伸出的练习建议

如果你已经理解了这两道题的核心思路，我建议你按下面的顺序做一些延伸练习，巩固"利用数据性质缩小搜索空间"这个思维模型：

第一层，把"找出数组中重复的数"改成"找出数组中所有重复的数"。这时候哈希表法需要调整，原地交换法也需要调整——因为找到一个重复后不能立即返回，需要继续处理。你可以想想怎么在 O(n) 时间内完成。

第二层，把"找出数组中重复的数"改成"找出数组中缺失的数"。如果数组长度为 n，数字范围是 1 到 n+1，缺失了一个数，怎么找？如果缺失了两个数呢？这时候二分答案法的优势就体现出来了。

第三层，把"二维数组中的查找"改成"统计二维数组中小于等于目标值的元素个数"。这个变形直接对应"有序矩阵第 K 小"中的统计步骤，是很好的过渡练习。

第四层，把二维数组的条件改成"每行递增，但第一列也递增，其他列没有保证"。这时候右上角出发的解法失效了，你需要想别的办法。这个练习的目的是让你理解解法的适用边界。

我在带新人的时候发现，很多人刷题喜欢追求数量——刷了三百道、五百道——但遇到新题还是不会。问题不在于刷得不够多，而在于每道题做完之后没有提炼出可迁移的思维模型。这两道题就是一个很好的例子：它们表面上考的是数组和矩阵，实际上考的是"如何利用数据的结构性性质来设计算法"。把这个思维模型吃透了，后面遇到类似的问题，你就能自己推导出解法，而不是靠回忆模板。

最后分享一个我个人的习惯：每做完一道有意思的题，我会用一两句话写下"这道题的核心洞察是什么"。比如这两道题，我的笔记是："找重复——利用数值范围做原地哈希或二分；二维查找——利用行列有序性，从鞍点出发每步排除一行或一列。"这两句话看起来简单，但在我后来遇到变形题的时候，往往就是靠这两句话快速定位到思路方向。