企业官网建设流程全解析

• 教程

数列查找是算法面试中覆盖面最广的题型之一：从「超过一半的数」「唯一重复元素」这类位运算与环检测问题，到「Top-K」「第 K 大」「旋转数组二分」「1 出现次数」这类复杂度与思维并重的经典题，几乎每家公司的笔面试题库里都会出现。本指南基于 Learn-Algorithms 仓库的 5.4 数列-查找.md 展开，结合仓库内源码与相关章节（5 数组数列问题、Top-K 问题、查找算法），逐题给出思路、复杂度分析与可运行代码，帮助你建立起「看到数列题先想位运算 / 二分 / 堆 / 快慢指针」的解题框架。

一、数组中超过出现次数一半的数字

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

思路：+-1 计数法（摩尔投票）

经典解法是「+-1 计数法」（即摩尔投票法，Boyer-Moore Majority Vote）：

• 维护一个候选值candidate和一个计数器count；
• 遍历数组：若count == 0，把当前元素设为候选值；若当前元素等于候选值则count++，否则count--；
• 因为目标数字出现次数超过一半，正负抵消后最终剩下的候选值一定是它。

时间复杂度 O(n)，空间复杂度 O(1)，不需要额外存储。

二、找数组里重复的一个数

题目：一个含 n 个元素的整数数组至少存在一个重复数，要求在 O(n) 时间内找出其中任意一个重复数。

文档给出了三条由浅入深的路线：

1. Hash 算法：空间复杂度 O(n)。文档特别提醒——数组元素要是 int 类型，且数的大小范围和数组长度 N 都可以是无穷大，此时哈希表空间可能无法满足条件，属于「空间换时间」但空间不可控的方案。
2. 先排序再遍历：复杂度 O(nlogn)，排序之后相邻元素相同即可判定重复。排序模板可以参考仓库 6 Sort/README.md 中的各类排序实现。
3. 高级解法：转化为「判断单链表中是否存在环」：把数组看作一个函数映射 f(i) = a[i]，即从下标 i 指向值 a[i] 的下标。由于存在重复数，映射必然成环。用快慢指针找到环的入口，入口处即重复元素。时间复杂度 O(n)、空间 O(1)，是面试官最想看到的加分答案。仓库 9 Algorithms Job Interview/README.md 给出了判断链表是否有环的快慢指针模板hasCycle，可直接借鉴其「快指针走两步、慢指针走一步、相遇即成环」的思想。

类似问题：找出数组中唯一的重复元素——思路同上，同样可以用环检测定位重复值。

三、查找只出现一次的元素

题目：给一个非空整数数组，比如 [2, 2, 3]，其余元素均出现 2 次，找出那个只出现一次的元素。

思路：异或运算

异或运算满足交换律和结合律，且x ^ x = 0、x ^ 0 = x。把所有元素异或一遍：成对的数字变成 0，落单的数字与 0 异或还是它本身。时间复杂度 O(n)，空间 O(1)。

int singleNumber(vector<int>& nums) { int res = 0; for (int n : nums) { res ^= n; } return res; }

这道题是「位运算解决数列问题」的代表，仓库 4 数值问题.md 将位运算列为数值类问题的三大主题之一，异或技巧在其中反复出现。

四、排序数组中某数字出现的次数

题目：在排序数组中找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中 2 的出现次数是 3 次。

分析

1. 因为是排序数组，必须使用二分查找，复杂度 O(logn)；
2. 关键技巧是「将二分查找坚持到底」：不要找到一个 target 就提前返回，而是分别二分出第一次出现位置和最后一次出现位置，两者之差加 1 即为次数。文档强调：在最坏情况下（如全数组都是 [2,2,2,2,2,2,2]），普通二分退化到线性，而「坚持到底」的边界二分依然保持 O(lgn) 复杂度。

int binary_search_first(int *a, int length, int key); // 左侧边界 int binary_search_lash(int *a, int length, int key); // 右侧边界

仓库 7 Search/README.md 给出了二分查找的边界细节：找到 target 时不要立即返回，而是把搜索区间上界right = mid继续向左压缩，最终left就是左侧边界；同时强调mid+1 / mid-1的细节，否则可能出现死循环。文中还对比了mid = (low+high)/2与mid = left + (right-left)/2的写法区别（后者可防溢出）。9 Algorithms Job Interview/README.md 中还有一份与之配套的bsearch二分模板。

五、大于 K 的最小正整数

题目：给定一个集合 A=[0,1,3,8]（元素都在 0~9 之间，但未必全部包含），指定任意正整数 K，请用 A 中的元素组成一个大于 K 的最小正整数。比如 A=[1,0]、K=21 时输出应为 100。

这是一道典型的「按位构造 + 贪心」题，文档未给出完整代码，但核心分析思路是：

• 先把 A 排序并去重；
• 若 A 中存在大于 K 最高位的数字，则取「比 K 最高位大的最小数字」+ 全 0 补位，即为答案（如 100 之于 21）；
• 否则逐位进位、递归处理更长位数，保证用 A 中元素组成且严格大于 K。

这类题检验的是对「数字位数与字典序」关系的理解，属于数列查找中偏数学构造的变体。

六、查找最小的 k 个元素（Top-K）

题目：输入 n 个整数，输出其中最小的 k 个。例如输入 1~8 这 8 个数字，最小的 4 个数字为 1、2、3、4。

topMinK(int *a, int length, int k); topMaxK(int *a, int length, int k);

文档给出了三条递进路线：

1. 全部排序：复杂度 O(NlogN)。数据量较大时，内存可能承受不住——比如 2 亿个整数全部装入内存再排序，代价过高。
2. 部分排序：维护一个大小为 K、由大到小排序的数组，遍历所有数据，每个数据与数组中最小元素比较，比最小元素大则插入并移动元素。复杂度 O(N*K)，且寻找插入位置、移动数组元素都有额外 CPU 消耗。
3. 堆排序（推荐）：需要一个既能快速查找、又能快速移动元素的数据结构，最好 O(1) 完成查找——答案就是二叉堆。遍历所有元素与堆顶比较（小根堆的堆顶是最小值，大根堆的堆顶是最大值），O(1) 完成查找，O(logk) 调整堆结构，整体复杂度O(n*logk)。

文档给出了最重要的选型口诀：

top-k 小的时候用大根堆，top-k 大的时候用小根堆。

原因：求最小的 k 个，维护一个容量为 k 的大根堆，堆顶是当前 k 个候选中最大的；只有比堆顶小才可能进入前 k 小，插入后淘汰堆顶，保证堆内始终是最小的 k 个。求最大的 k 个则相反。

堆的底层原理可参考仓库 4 Tree/8-堆/堆.md：堆是「优先队列/二叉堆」，用数组存储的完全二叉树，i 节点的父节点索引为 (i-1)/2，左右子节点为 2i+1、2i+2；插入删除后通过上浮（swim）/下沉（sink）维护堆次序。仓库 4 Tree/8-堆/Top-K 问题.md 也对本题做了呼应：TopK 大问题用固定 k 个元素的小根堆，遍历剩余数据时「插入小根堆并调整堆」，保证堆内 k 个元素始终是当前最大的 k 个。

七、找第 k 大的数

题目：比如 1~8 这 8 个数字，第 3 大的数字是 6。

int topK(int *a, int length, int k)

解法一：冒泡局部排序

只做 k 趟冒泡，第 k 趟结束后倒数第 k 个位置即为第 k 大。时间复杂度 O(k*n)，k 较小时很实用：

// 冒泡实现 public int findK(int[] nums, int k){ // base case if (nums == null || nums.length < k) { return -1; } for (int i = 1; i <= k; i++){ for (int j = 0; j < nums.length - i; j++) { int next = j + 1; if (nums[j] > nums[next]){ int tmp = nums[j]; nums[j] = nums[next]; nums[next] = tmp; } } } return nums[nums.length - k]; }

解法二：小根堆维护 Top-K

维护一个容量为 k 的小根堆，堆内始终是遍历过程中遇到的「最大的 k 个」候选，遍历结束后堆顶就是第 k 大：

/** * 小根堆实现 */ public static int findMaxK(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a, b) -> (a - b)); for (int i = 0; i < nums.length; i++) { // 取出前k个元素放入 PQ 中 if (i < k) { pq.add(nums[i]); continue; } Integer head = pq.peek(); if (head < nums[i]) { // 维护 priorityQueue 中元素只有k个 pq.poll(); pq.add(nums[i]); } } return pq.poll(); }

Java 的PriorityQueue就是基于小根堆（二叉堆）实现的优先队列，其特性与 API 在仓库 4 Tree/8-堆/堆.md 有完整说明：add/offer插入元素、poll取出并删除堆头、peek只读堆头、remove删除指定元素；且它不是线程安全的，并发环境需用PriorityBlockingQueue。需要注意，这段代码中pq的容量与堆大小随 k 变化，实际工程中可显式保证堆容量上限为 k。

八、最长公共子序列与相邻元素最大/最小差

文档在「最长公共子序列（动态规划的经典题目）」标题下，实际整理了【最大/小差问题】：

题目：求相邻元素的最大差值。有无序实数列 V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间。例如 【9, -1, -11, 2】 中，最大差值 = 2 - (-11) = 13（排序后相邻元素的最大间隙）。

文档给出的思路：

• 最小差 hash 合并：若允许重复值，最小差直接为 0；不重复时用哈希/桶思想找相邻最近值；
• 最大差 hash 分解：利用**桶排序（鸽笼原理）**将数值均匀分桶，最大值与最小值所在桶之间的空桶两侧元素差即为候选最大间隙，无需真正全排序即可线性求解；
• 文档强调：桶排序比快排还快，但最耗空间——它用空间换时间，在线性时间求最大差这类问题中尤其有效。

动态规划模板可参考仓库 8 Algorithms Analysis/动态规划.md。

九、最长递增子序列

题目描述：设 L = <a1, a2, …, an> 是 n 个不同的实数的序列，L 的递增子序列是这样一个子序列 Lin = <aK1, aK2, …, aKm>，其中 k1 < k2 < … < km 且 aK1 < aK2 < … < aKm。求最大的 m 值。

如 【5, 6, 7, 3, 2, 8】 的最长子序列为 【5, 6, 7, 8】，答案为 4。

思路：动态规划。定义 dp[i] 为以第 i 个元素结尾的最长递增子序列长度，状态转移为：dp[i] = max(dp[j] + 1)，其中 j < i 且 a[j] < a[i]。O(n²) 的 DP 可解，更优做法是「贪心 + 二分」维护一个递增的辅助数组（tails），可将复杂度优化到 O(nlogn)。仓库 5 数组数列问题.md 还给出了最长递减子序列的同型题（{9,4,3,2,5,4,3,2} 的最长递减子序列为 {9,5,4,3,2}），与本题互为镜像。

十、在从 1 到 n 的正数中 1 出现的次数

题目：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1、10、11 和 12，1 一共出现了 5 次。

文档指出这是一道广为流传的 Google 面试题：

int one_appear_count(int n);

• 思路 1：遍历 1~n，统计每个数中出现 1 的个数。n 足够大时效率很低，复杂度 O(n*logn)；
• 思路 2：分析规律。按位统计：分别统计个位、十位、百位……上 1 出现的次数，利用「当前位数字为 0/1/大于 1」三种情况分段计算，复杂度 O(logn)，即「数学归纳法」式的数位统计。

仓库中可佐证位运算统计技巧：9 Algorithms Job Interview/codes/4 numer/one_appear_count_by_binary.c 通过num &= num - 1循环清掉最低位的 1 来统计二进制中 1 的个数，展示了位运算在计数类题目中的高效性——十进制「1 的出现次数」与之共享「逐位分解 + 规律统计」的核心思维。

十一、搜索旋转排序数组

题目：整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。给定旋转后的数组 nums 和一个整数 target，如果 nums 中存在 target 则返回其下标，否则返回 -1。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

解法核心：仍是二分查找。虽然整个数组不是完全有序，但旋转后数组被分界点切成两段，每一段内部都是升序。二分时先判断nums[mid]落在左段还是右段：

• 若nums[low] <= nums[mid]，说明左半段有序：若nums[low] <= target < nums[mid]则向右半区间收缩，否则向左；
• 否则右半段有序：若nums[mid] < target <= nums[high]则向左半区间收缩，否则向右。

每次迭代都能排除一半的搜索区间，因此整体时间复杂度 O(logn)，空间 O(1)。仓库 5 数组数列问题.md 中「递减数列左移后的数组中找数」「旋转数组中的最小元素」两道题与本题同源，都利用了「旋转数组局部有序」的性质，二分思想互相印证；二分细节（low/high 边界、mid 取值防溢出）可对照 7 Search/README.md 中的模板。

总结：数列查找的通用解题框架

回顾 5.4 数列-查找.md 的全部题目，可以提炼出面试中应对数列查找题的优先级框架（与仓库 5 数组数列问题.md 开篇的思路清单一致）：

做题时的通用顺序建议：先判断数据是否有序（决定是否二分），再判断元素取值域是否有限（决定是否哈希/桶），接着看是否需要「只存 k 个候选」（决定是否堆），最后考虑元素间是否存在函数映射关系（决定是否快慢指针/环检测）。掌握了这四步，数列查找题就基本不再有陌生面孔。

延伸阅读

• 5 数组数列问题.md：数组排序、子数组、交并集等更多数列题型
• Top-K 问题.md：堆解法在 TopK 问题上的集中讨论
• 堆.md：二叉堆存储结构、堆调整与 Java PriorityQueue 详解
• 查找算法：顺序/二分/分块/动态/哈希五种查找算法总览
• 动态规划.md：LIS、LCS 等动态规划题型的通用模板

• 教程