如何高效掌握二分、哈希表、堆、优先队列等面试高频算法题？

本文将覆盖 二分 + 哈希表 + 堆 + 优先队列 方面的面试算法题，文中我将给出： 面试中的题目 解题的思路 特定问题的技巧和注意事项 考察的知识点及其概念 详细的代码和解析 在开始之前，我们先看下会有哪些重点内容： 现在就让我们开始吧！ 二分 概念： 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。 基本思路： 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较 如果两者相等，则查找成功 否则利用中间位置记录将表分成前、后两个子表 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表 否则进一步查找后一子表 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 二分搜索 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 技巧： 分析二分查找的一个技巧是： 不要出现 else，而是把所有情况用 if / else if 写清楚 这样可以清楚地展现所有细节。 这里我们以递归和非递归方式，解决面试中的二分搜索题 递归 思路很简单： 判断起始点是否大于终止点 比较 nums[mid] 与目标值大小 如果 nums[mid] 大，说明目标值 target 在前面 反之如果 nums[mid] 小，说明目标值 target 在前面后面 如果既不大也不小，说明相等，则返回当前位置 class Solution { public int search(int[] nums, int target) { return binarySearch(nums, 0, nums.length - 1, target); } private int binarySearch(int[] nums, int start, int end, int target) { if(start > end) { return -1; } int mid = (end + start) / 2; if(nums[mid] < target) { return binarySearch(nums, mid + 1, end, target); } if(nums[mid] > target) { return binarySearch(nums, start, mid - 1, target); } return mid; } } 非递归 这个场景是最简单的: 搜索一个数 如果存在, 返回其索引 否则返回 -1 int binarySearch(int[] nums, int target) { int left = 0; // 注意减 1 int right = nums.length - 1; while(left <= right) { int mid = (right + left) / 2; if(nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; // 注意 else if (nums[mid] > target) right = mid - 1; // 注意 } return -1; } 相关视频 分钟教你二分查找(python版) X的平方根 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。