梦会绽放

题解

/ 注册

全部文章 / 题解（共5篇）

Java实现#寻找峰值#

从此题中得到的小感悟：充分把握题意方能选用更合适的解题方法（类二分法）此题难度中等，很容易想到思路1，但是仅此的话，不符合“中等”的标签；另外，题中要求时间复杂度为 O(log n)，这让我们很自然地联想到二分法，我们所熟悉的二分法是基于有序表，这道题目数组并不一定有序，那又如何和二分法产生关...

Java 数组二分查找

2022-02-10

3 602

题解 | #<比较详细了吧>求平方根#

思路1：二分法。初始low=1, high的初始化有讲究：若x大于4，high初始化为x/2; 若x<=4，high初始化为x. 至少这样可加速查找过程。（证明很简单，见下图）若mid*mid <= x,接着判断 (1)若(mid+1)^2>x,则返回mid; ...

Java 数学二分查找二分法迭代

2022-01-30

2 596

题解 | #<图示详解>在旋转过的有序数组中寻找目标值#

思路：二分法我们知道二分法适用于有序数组，并且题中告诉我们数组严格升序，只是经过了旋转，经过一番思考，我们可以充分利用好以上性质，写出让面试官想要的代码。旋转后的数组分为两部分，[low...mid]和[mid...high]，这两部分必有一个是有序数组，我们考虑每次都处理有序的那部分，...

Java 分治数组二分查找

2022-01-29

1 498

题解 | #二叉搜索树的最近公共祖先#

简单容易写思路：非递归，利用二叉搜索树的特点。左子树<根节点<右子树若p,q都比当前结点的值小，说明最近公共祖先结点在当前结点的左子树上，继续检查左子树；若p,q都比当前结点的值大，说明最近公共祖先结点在当前结点的右子树上，继续检查右子树；若p,q中一个比当前结点的值大，另一个...

Java 二叉树二叉搜索树二分查找

2022-01-11

30 1303

题解 | #二分查找-II#

算法思想：设置 low 和 high 两个指针，mid每次指向区间中间的元素，即 mid = low+(low+high)/2 ( 这里采用此形式而不是使用 mid=(low+high)/2 ，是为了防止 int 型数据的溢出)，如果 mid 所指的值大于 target，则在左半区间[low,mid...

C 二分查找

2022-01-01

0 404