两道经典数组算法题精讲：重复数字查找与二维数组搜索

1. 从两道题说起为什么它们总被放在一起考找出数组中重复的数和二维数组中的查找这两道题放在一起看其实特别有意思。前者考的是你对原地算法和空间换时间的理解后者考的是你对数据有序性的敏感度。它们都属于那种看起来简单写起来容易翻车的典型题目。我第一次接触这两道题的时候心里想的是这不就是遍历吗一个用哈希表一个逐行二分能有多难结果面试的时候被追问能不能不用额外空间、时间复杂度能不能再降当场就卡壳了。后来刷题刷多了才发现这两道题背后藏着的东西远比表面看起来深——它们分别对应了数组类问题的两大核心思路下标映射和有序性利用。这篇文章我会把这两道题彻底拆开从暴力解法一路讲到最优解把每一步的思考过程、参数选择、边界处理都讲清楚。不管你是刚开始刷题的新手还是想重新梳理思路的老手应该都能从中找到有用的东西。尤其是那些为什么这么想的部分我会尽量讲透因为解题思路比代码本身重要得多。2. 找出数组中重复的数从哈希表到原地交换2.1 题目描述与核心约束先把题目说清楚。给定一个长度为 n 的数组 nums里面所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。要求找出数组中任意一个重复的数字。举个例子nums [2, 3, 1, 0, 2, 5, 3]长度是 7所有数字都在 0 到 6 之间。这里面 2 和 3 都是重复的返回其中任意一个就行。这道题有一个非常关键的约束数字范围是 0 到 n-1。很多人第一眼看到这个条件会忽略掉觉得只是个普通的数组。但恰恰是这个条件决定了你能不能写出空间复杂度 O(1) 的解法。如果数字范围不是 0 到 n-1那原地交换的思路就完全不成立了。注意题目说找出任意一个重复的数字就够了不需要找出所有重复的数字也不需要统计重复次数。这个细节很重要它意味着你不需要完整遍历整个数组找到就可以直接返回。2.2 思路一排序后相邻比较最直观的做法是什么排序。排完之后重复的数字一定相邻扫一遍就行了。def find_duplicate_sort(nums): nums.sort() for i in range(1, len(nums)): if nums[i] nums[i - 1]: return nums[i] return -1这个解法的时间复杂度是 O(n log n)空间复杂度取决于排序算法Python 的 sort 是 Timsort最坏情况需要 O(n) 的额外空间。优点是简单不容易写错。缺点是时间复杂度不够好而且会修改原数组。如果面试官问你能不能不修改原数组这个解法就直接出局了。2.3 思路二哈希表记录出现次数第二个想到的肯定是哈希表。遍历数组用一个集合记录已经出现过的数字如果当前数字已经在集合里了直接返回。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(n) 空间。如果面试官说空间复杂度能不能降到 O(1)你就得换思路了。2.4 思路三原地交换下标映射法这才是这道题的精髓所在。核心思想是这样的因为数字范围是 0 到 n-1所以如果没有重复数字每个数字 i 应该正好放在下标 i 的位置上。也就是说nums[i] i 应该对所有 i 成立。那如果有重复数字呢说明某个位置上的数字不对而另一个数字占了两个位置。我们可以通过不断交换把每个数字放到它应该在的位置上。交换过程中如果发现目标位置上已经有了正确的数字那就找到了重复。具体流程是这样的从下标 0 开始遍历。如果 nums[i] i说明这个位置已经对了跳过。如果 nums[i] ! i检查 nums[nums[i]] 是否等于 nums[i]。如果相等说明 nums[i] 这个数字在它应该在的位置上已经有一个了找到了重复直接返回。如果不等交换 nums[i] 和 nums[nums[i]]把 nums[i] 放到正确的位置上。交换后继续在当前下标检查因为换过来的新数字可能也不对。def find_duplicate_swap(nums): i 0 while i len(nums): if nums[i] i: i 1 continue if nums[nums[i]] nums[i]: return nums[i] # 交换 nums[nums[i]], nums[i] nums[i], nums[nums[i]] return -1这个解法的时间复杂度是 O(n)。虽然有一个 while 循环里面套了交换操作但每个数字最多被交换两次就能放到正确的位置上所以总的交换次数是 O(n) 的。空间复杂度是 O(1)完全原地操作。实操心得写交换的时候一定要注意顺序。nums[nums[i]], nums[i] nums[i], nums[nums[i]]这个写法在 Python 里是对的因为右边先求值。但在 C 或 Java 里你得用临时变量否则会出错。我见过太多人在这里翻车。2.5 二分查找的思路不修改数组的 O(1) 空间解法如果面试官加一个条件不能修改原数组且空间复杂度 O(1)那原地交换就不能用了。这时候可以用二分查找的思路。思路是这样的数字范围是 0 到 n-1我们可以统计数组中落在某个区间 [left, right] 内的数字个数。如果个数大于区间长度说明重复数字在这个区间内。然后缩小范围继续找。def find_duplicate_binary(nums): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 count sum(1 for num in nums if left num mid) if count mid - left 1: right mid else: left mid 1 return left时间复杂度是 O(n log n)因为每次统计需要遍历整个数组二分需要 log n 次。空间复杂度 O(1)。这个解法不修改原数组但时间上比原地交换慢一些。注意二分查找解法有一个前提就是数字范围必须是 0 到 n-1。如果范围变了这个解法就不适用了。而且这个解法只能找到一个重复数字不能保证找到所有。2.6 三种解法的对比与选择解法时间复杂度空间复杂度是否修改原数组适用场景排序O(n log n)O(n)是快速实现不要求最优哈希表O(n)O(n)否通用数字范围无限制原地交换O(n)O(1)是数字范围 0~n-1允许修改二分查找O(n log n)O(1)否不允许修改数组范围 0~n-1实际面试中我一般会先写哈希表解法保证正确性然后根据面试官的追问逐步优化。如果面试官直接问能不能 O(1) 空间那就上原地交换。如果再加不能修改数组那就上二分。3. 二维数组中的查找有序性带来的降维打击3.1 题目描述与关键条件题目是这样的在一个二维数组中每一行都按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有该整数。举个例子1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15查找 7 返回 true查找 5 返回 false。这道题的关键在于每一行从左到右递增每一列从上到下递增。注意不是整个二维数组全局有序而是行和列分别有序。这个条件比全局有序弱但比完全无序强得多。很多人第一反应是逐行二分查找。每一行都是有序的对每一行做二分时间复杂度是 O(m log n)其中 m 是行数n 是列数。这个解法不算差但还不是最优的。3.2 暴力遍历与逐行二分暴力遍历就是两层循环时间复杂度 O(mn)基本不用考虑除非数组特别小。逐行二分稍微好一点def search_matrix_binary(matrix, target): for row in matrix: left, right 0, len(row) - 1 while left right: mid (left right) // 2 if row[mid] target: return True elif row[mid] target: left mid 1 else: right mid - 1 return False时间复杂度 O(m log n)空间复杂度 O(1)。这个解法利用了行的有序性但没有利用列的有序性。如果面试官追问能不能利用列也有序这个条件你就需要换思路了。3.3 右上角起始的线性查找这是这道题的最优解也是最能体现有序性利用精髓的解法。核心思想是从右上角开始查找。为什么是右上角因为右上角这个位置很特殊——它是当前行的最大值同时是当前列的最小值。具体流程从右上角 (0, n-1) 开始。如果当前元素等于目标值返回 true。如果当前元素大于目标值说明目标值不可能在这一列因为这一列从上到下递增当前元素已经是这一列最小的了下面的只会更大所以向左移动一列。如果当前元素小于目标值说明目标值不可能在这一行因为这一行从左到右递增当前元素已经是这一行最大的了左边的只会更小所以向下移动一行。重复直到越界返回 false。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)因为每次要么向左一列要么向下一行最多走 m n 步。空间复杂度 O(1)。这个解法同时利用了行和列的有序性是最优解。实操心得为什么选右上角而不是左下角其实左下角也可以思路完全对称。左下角是当前行的最小值当前列的最大值。如果当前元素大于目标值向上移动如果小于目标值向右移动。但右上角更符合直觉因为从大到小排除列从小到大排除行这个逻辑比较顺。3.4 为什么不能从左上角或右下角开始这个问题我被问过好几次。从左上角开始当前元素是全局最小值。如果目标值比它大你既不能排除行也不能排除列因为右边和下边都可能包含目标值。这就退化成暴力搜索了。右下角同理当前元素是全局最大值。如果目标值比它小你既不能排除行也不能排除列因为左边和上边都可能包含目标值。所以关键点是起始位置必须能够让你在每次比较后明确排除一行或一列。右上角和左下角满足这个条件左上角和右下角不满足。3.5 边界条件与特殊输入处理这道题有几个容易翻车的边界条件矩阵为空matrix []直接返回 false。矩阵只有一行或一列逻辑仍然成立但要注意行列索引不要越界。矩阵中所有元素相同如果目标值等于这个元素返回 true否则在右上角比较后就会一直移动直到越界。目标值比矩阵中所有元素都小或都大会一直移动直到越界返回 false。# 边界测试用例 assert search_matrix([], 5) False assert search_matrix([[]], 5) False assert search_matrix([[1]], 1) True assert search_matrix([[1]], 2) False assert search_matrix([[1, 2, 3]], 2) True assert search_matrix([[1], [2], [3]], 2) True注意Python 中if not matrix or not matrix[0]这个判断很关键。如果只写if not matrix当 matrix 是[[]]的时候会通过检查然后在len(matrix[0])那里报 IndexError。我踩过这个坑排查了半天才发现是空行的问题。4. 两道题的共通思维有序性与下标映射4.1 下标映射的本质找出数组中重复的数的原地交换解法本质上是利用了数字与下标的一一对应关系。因为数字范围是 0 到 n-1所以每个数字都有一个应该在的位置。通过交换把数字放到正确的位置上就能在 O(n) 时间内找到重复。这种思路在很多数组类问题中都有应用。比如缺失的第一个正数、找到所有数组中消失的数字等都是利用下标映射来做到 O(1) 空间。核心条件是元素的取值范围和数组长度有明确的对应关系。如果这个条件不满足下标映射就用不了。4.2 有序性利用的通用套路二维数组中的查找利用的是行和列分别有序这个条件。通过从右上角开始每次比较都能排除一行或一列把 O(mn) 的暴力搜索降到 O(mn)。有序性利用的通用套路是找到一个起始点使得每次比较后能排除一部分搜索空间。一维有序数组的二分查找是这个套路的最简单形式二维有序矩阵的右上角查找是它的二维扩展。类似的题目还有搜索旋转排序数组、寻找峰值等都是利用局部有序性来缩小搜索范围。4.3 空间换时间的取舍这两道题都涉及一个核心取舍要不要用额外空间来换时间。哈希表解法用 O(n) 空间换 O(n) 时间原地交换用 O(1) 空间但也做到了 O(n) 时间。二分查找用 O(1) 空间但时间是 O(n log n)。实际做题时我一般会先问清楚约束条件能不能修改原数组空间复杂度有没有要求时间复杂度有没有要求根据这些条件来选择最合适的解法。实操心得面试的时候不要一上来就写最优解。先写一个能跑的暴力解然后逐步优化。这样既能保证有东西可写又能展示你的思考过程。面试官更看重的是你的思路而不是你能不能背出最优解的代码。5. 常见问题与排查技巧实录5.1 原地交换法为什么会死循环原地交换法最容易出的问题就是死循环。我一开始写的时候交换完之后没有正确处理当前下标导致一直在同一个位置打转。问题出在这里交换之后当前位置的数字变了但你可能还需要继续检查这个位置。如果你直接i 1就会漏掉一些情况。正确的做法是交换之后不移动 i继续在当前下标检查。只有当nums[i] i的时候才移动 i。# 错误写法交换后直接 i 1 while i len(nums): if nums[i] ! i: nums[nums[i]], nums[i] nums[i], nums[nums[i]] i 1 # 这里可能跳过需要检查的位置 # 正确写法交换后不移动 i while i len(nums): if nums[i] i: i 1 elif nums[nums[i]] nums[i]: return nums[i] else: nums[nums[i]], nums[i] nums[i], nums[nums[i]]5.2 二维数组查找的越界问题二维数组查找最常见的 bug 是数组越界。尤其是在矩阵为空、只有一行、只有一列的情况下很容易出现 IndexError。排查的时候我一般会先加边界检查然后用小规模的测试用例逐步验证。比如先用 1x1 的矩阵测试再用 1xN 和 Nx1 的矩阵测试最后用完整的矩阵测试。问题现象可能原因排查方法IndexError矩阵为空或空行检查not matrix or not matrix[0]结果错误行列索引搞反了打印每次移动后的 row 和 col死循环移动方向搞反了检查大于和小于时的移动逻辑漏解起始位置选错了确认从右上角或左下角开始5.3 二分查找的边界处理二分查找的边界处理是出了名的容易出错。left right还是left rightmid 1还是mid这些细节稍不注意就会导致死循环或漏解。我的经验是统一使用左闭右闭区间即left rightright mid - 1left mid 1。这样不容易出错。# 左闭右闭的标准写法 left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1注意mid (left right) // 2在 Python 中不会溢出但在 C 或 Java 中如果 left 和 right 都很大可能会溢出。安全的写法是mid left (right - left) // 2。5.4 面试中的追问与应对这两道题在面试中经常会有追问。我整理了一些常见的追问和应对思路追问一如果数组中有多个重复数字怎么找出所有对于找出数组中重复的数如果需要找出所有重复数字哈希表解法最直接。原地交换法也可以但需要额外处理因为找到一个重复后不能直接返回要继续扫描。追问二如果数字范围不是 0 到 n-1 呢那原地交换和二分查找都不能用了只能用哈希表或排序。这也是为什么面试官会先给出数字范围这个条件——它决定了你能用哪些解法。追问三二维数组如果行和列不是分别有序而是全局有序呢如果整个二维数组全局有序按行展开后是一个有序一维数组那可以直接把二维数组当作一维数组做二分查找时间复杂度 O(log(mn))。追问四如果二维数组的行数和列数非常大内存放不下怎么办这是一个系统设计类的问题。可以考虑分块读取或者用外部排序的思路。不过一般面试中不会问到这么深除非是专门考系统设计的岗位。6. 从刷题到实战这些思路还能用在哪6.1 数据去重与重复检测找出数组中重复的数的思路在实际工作中非常常见。比如日志分析中检测重复请求、数据清洗中找出重复记录、用户行为分析中识别异常重复操作等。哈希表解法是最通用的适合大多数场景。如果数据量特别大内存放不下可以考虑用布隆过滤器做初步筛选或者用外部排序后相邻比较。原地交换法的思路在特定场景下也很有用。比如数据本身就是按某种规则编号的你可以利用编号和存储位置的对应关系来快速检测重复。6.2 有序矩阵的快速检索二维数组中的查找的思路在数据库索引、图像处理、游戏地图寻路等场景中都有应用。比如在一个按行按列都有序的评分矩阵中查找某个分数或者在一个按时间和优先级排序的任务队列中查找特定任务都可以用类似的思路。核心思想是利用数据的局部有序性每次比较排除一部分搜索空间。这个思想不仅适用于二维数组也适用于更高维度的有序结构。6.3 算法思维的迁移这两道题教给我们的不只是具体的解法更是一种思维方式观察数据特征数字范围、有序性、重复性这些特征决定了你能用什么算法。权衡时空复杂度没有绝对最优的解法只有最适合当前约束的解法。从暴力到最优先写出能跑的解法再逐步优化这是解决所有算法问题的通用路径。我在实际工作中遇到性能问题时经常会回想这两道题的思路。比如一个查询很慢我会先想数据有没有有序性可以利用能不能用空间换时间能不能通过某种映射关系把 O(n) 降到 O(1)这些思维方式比具体的代码更有价值。代码会过时但思考问题的方式不会。最后分享一个我刷题时的小习惯每做完一道题我会问自己三个问题——这道题的核心条件是什么如果条件变了解法要怎么调整这道题的思路还能用在哪些地方这三个问题能帮我把一道题吃透而不是做完就忘。