教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载数列查找是算法面试中覆盖面最广的题型之一从「超过一半的数」「唯一重复元素」这类位运算与环检测问题到「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) 时间内找出其中任意一个重复数。文档给出了三条由浅入深的路线Hash 算法空间复杂度 O(n)。文档特别提醒——数组元素要是 int 类型且数的大小范围和数组长度 N 都可以是无穷大此时哈希表空间可能无法满足条件属于「空间换时间」但空间不可控的方案。先排序再遍历复杂度 O(nlogn)排序之后相邻元素相同即可判定重复。排序模板可以参考仓库 6 Sort/README.md 中的各类排序实现。高级解法转化为「判断单链表中是否存在环」把数组看作一个函数映射 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(vectorint nums) { int res 0; for (int n : nums) { res ^ n; } return res; }这道题是「位运算解决数列问题」的代表仓库 4 数值问题.md 将位运算列为数值类问题的三大主题之一异或技巧在其中反复出现。四、排序数组中某数字出现的次数题目在排序数组中找出给定数字的出现次数比如 [1, 2, 2, 2, 3] 中 2 的出现次数是 3 次。分析因为是排序数组必须使用二分查找复杂度 O(logn)关键技巧是「将二分查找坚持到底」不要找到一个 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就是左侧边界同时强调mid1 / mid-1的细节否则可能出现死循环。文中还对比了mid (lowhigh)/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]、K21 时输出应为 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);文档给出了三条递进路线全部排序复杂度 O(NlogN)。数据量较大时内存可能承受不住——比如 2 亿个整数全部装入内存再排序代价过高。部分排序维护一个大小为 K、由大到小排序的数组遍历所有数据每个数据与数组中最小元素比较比最小元素大则插入并移动元素。复杂度 O(N*K)且寻找插入位置、移动数组元素都有额外 CPU 消耗。堆排序推荐需要一个既能快速查找、又能快速移动元素的数据结构最好 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左右子节点为 2i1、2i2插入删除后通过上浮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) { PriorityQueueInteger 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 和 121 一共出现了 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 在预先未知的某个下标 k0 k nums.length上进行了旋转使数组变为 [nums[k], nums[k1], …, 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 开篇的思路清单一致场景首选武器复杂度代表题唯一/成对/重复元素位运算异或、快慢指针环检测O(n)/O(1)只出现一次的元素、找重复数有序数组二分查找含边界二分O(logn)出现次数、旋转排序数组Top-K / 第 K 大二叉堆大/小根堆O(n*logk)最小 k 个元素、第 k 大最大差 / 相邻差桶排序鸽笼原理O(n)相邻元素最大差值递增子序列类动态规划可优化为贪心二分O(n²)→O(nlogn)最长递增子序列数位计数类数学规律逐位统计O(logn)1 出现的次数构造最小整数类按位贪心—大于 K 的最小正整数做题时的通用顺序建议先判断数据是否有序决定是否二分再判断元素取值域是否有限决定是否哈希/桶接着看是否需要「只存 k 个候选」决定是否堆最后考虑元素间是否存在函数映射关系决定是否快慢指针/环检测。掌握了这四步数列查找题就基本不再有陌生面孔。延伸阅读5 数组数列问题.md数组排序、子数组、交并集等更多数列题型Top-K 问题.md堆解法在 TopK 问题上的集中讨论堆.md二叉堆存储结构、堆调整与 Java PriorityQueue 详解查找算法顺序/二分/分块/动态/哈希五种查找算法总览动态规划.mdLIS、LCS 等动态规划题型的通用模板赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Learn-Algorithms 面试题精讲堆与栈、队列的数据结构及五大经典算法题Learn Algorithms 面试题精讲堆与栈、队列的数据结构及五大经典算法题 导读 本文基于 Learn Algorithms https://lin教程免费开源5分钟掌握AMD Ryzen处理器专业级调试工具SMUDebugTool终极指南免费开源5分钟掌握AMD Ryzen处理器专业级调试工具SMUDebugTool终极指南 你是不是觉得自己的AMD Ryzen处理器性能总是差那么一点明教程Learn-Algorithms 算法面试笔记矩阵与二维数组五类高频题的解法与源码解析Learn Algorithms 算法面试笔记矩阵与二维数组五类高频题的解法与源码解析 本篇文章以 6 矩阵.md 为核心骨架整理展开并以仓库源码 prin教程上一篇小米MiNLP与主流NLP工具对比jieba、HanLP、LTP的优劣分析下一篇tsParticles 单色青色Monochrome Cyan调色板使用指南从安装、配色到引擎解析原理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考