写在前面
最近在练工作室的每日一题,目前正在二分查找阶段。其中第五天出的题是一道二分查找的综合题,他结合了前几天的知识点一起考察。LeetCode官方给这道题的TAG是困难。本人一开始看着觉得其实也不难,思路很明确,但是解题过程却很坎坷,基础不牢地动山摇,特此写一篇博客记录一下。

题目
给你一个山脉数组 mountainArr,请你返回能够使得 mountainArr.get(index) 等于 target 最小的下标 index 值。如果不存在这样的下标 index,就请返回 -1。
何为山脉数组?如果数组 A 是一个山脉数组的话,那它满足如下条件:首先,A.length >= 3;其次,在 0 < i < A.length - 1 条件下,存在 i 使得:A[0] < A[1] < ... A[i-1] < A[i],A[i] > A[i+1] > ... > A[A.length - 1]。
思路
解题思路很简单。
- 首先找到山脉的山峰元素下标,以此分割左山峰(单调递增)和右山峰(单调递减)
分割完毕后,先对左山峰进行二分查找target
- 如果左山峰查找成功,那么就直接返回下标index值
如果左山峰查找失败,再对右山峰进行二分查找target
- 如果右山峰查找成功,那么就直接返回下标Index值
- 如果右山峰查找失败,那么就返回-1表示查找失败
解题过程
Round 1:有问题
一开始按照上述思路进行代码编写,但是并不成功。二分的思路虽然很简单,但是真的很细节!!!
发现问题:
- Part 1中的
while
循环第二个条件直接使得整个循环无法进行 - Part 1中的
while
循环后的if块无任何意义。因为,既然这个是山峰数组,那么就必然能找到山峰元素。应该结合问题1,当找到山峰元素直接break
出循环即可
需要注意:
- 对于找右边数组,由于右边数组是单调递减的,当
midVal > target
时,midVal
是在target
的左边。因此,left = mid + 1
。
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
//Part 1:找到山峰元素索引
int left = 0;
int right = mountainArr.length() - 1;
int topIndex = -1;
while(left <= right && topIndex != -1){ //后项判断替代return ##兄弟你有问题!!!
int mid = right + (left - right) / 2;
//减少get方法调用,用变量缓存起来
int midVal = mountainArr.get(mid);
int midMinusVal = mountainArr.get(mid - 1);
int midPlusVal = mountainArr.get(mid + 1);
//刚好命中
if(midMinusVal < midVal && midVal > midPlusVal){
topIndex = mid;
}else if(midVal < midPlusVal){ //mid在左边
left = mid + 1;
}else{ //mid在右边
right = mid - 1;
}
}
if(topIndex == -1){ //##兄弟你有问题!!!
topIndex = left; //##兄弟你有问题!!!
} //##兄弟你有问题!!!
//Part 2:先找左边数组,左边数组有就结束,没有就继续到Part 3找右边数组
left = 0;
right = topIndex;
while(left <= right){
int mid = right + (left - right) / 2;
int midVal = mountainArr.get(mid);
if(midVal == target){
return mid; //左边数组有,且直接命中,结束
}else if(midVal > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
//Part 3:找右边数组,还是找不到的话返回-1
left = topIndex;
right = mountainArr.length() - 1;
while(left <= right){
int mid = right + (left - right) / 2;
int midVal = mountainArr.get(mid);
if(midVal == target){
return mid; //右边数组有,且直接命中,结束
}else if(midVal > target){
left = mid + 1; //#需要注意!!!
}else{
right = mid - 1;
}
}
//还找不到那就真的找不到了
return -1;
}
}
Round 2:还是有问题
按照上面存在的问题改了下,还是不行。找山峰元素依然用的是循环中找答案的二分查找方法。
发现问题:
- 在Part 1中,存在
mid = 0
的可能,如果进行mid - 1
运算的话,结果是-1
,会发生数组下溢(直到Round 5才解决)。
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
//Part 1:找到山峰元素索引
int topIndex = -1;
while(left <= right){
int mid = left + (right - left) / 2;
//减少get方法调用,用变量缓存起来
int midVal = mountainArr.get(mid);
int midMinusVal = mountainArr.get(mid - 1); //##兄弟你有问题!!!
int midPlusVal = mountainArr.get(mid + 1);
//刚好命中
if(midMinusVal < midVal && midVal > midPlusVal){
topIndex = mid;
break;
}else if(midVal < midPlusVal){ //mid在左边
left = mid + 1;
}else{ //mid在右边
right = mid - 1;
}
}
// 后面没有问题,省略...
}
}
Round 3:还是有问题,但是快可以了
在修改上述代码的时候,我一直不知道怎么解决,很是懵逼。
后来请教了Uni,说我找山峰元素有问题。然后看到他使用到了缩小可能存在区间的二分查找方法,我直接改用了也没管为什么,因为我当时实在是懵逼,不知道怎么解决。实际上,循环中找答案没有任何问题,只不过是我们需要排除存在mid = 0
的可能即可。
但是按照Uni的代码修改后,还是有问题,最后发现是我自己看走眼了。
发现问题:
- 发生了
index = mountArr.length()
的数组上溢。后来仔细对比,取mid元素下标的式子写成int mid = right + (left - right) / 2;
,而正确应该是int mid = left + (right- left ) / 2;
。前者是向下取整,后者是向后取整。如果是向下取整,当剩下只有两个元素时,mid
永远等于左元素,因此mid + 1
不会溢出。
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
//Part 1:找到山峰元素索引
int topIndex;
while(left < right){
int mid = right + (left - right) / 2; //##兄弟你有问题!!!
if(mountainArr.get(mid) < mountainArr.get(mid + 1)){
left = mid + 1;
}else{
right = mid;
}
}
topIndex = left;
// 后面没有问题,省略...
}
}
Round 4:终于解决了,但是有疑惑
通过修改成向下取整,终于解决了数组上溢的问题。注意:此时Round 2 中的数组下溢问题还没解决。
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
int left = 0;
int right = mountainArr.length() - 1;
//Part 1:找到山峰元素索引
int topIndex;
while(left < right){
int mid = left + (right - left) / 2;
if(mountainArr.get(mid) < mountainArr.get(mid + 1)){
left = mid + 1;
}else{
right = mid;
}
}
topIndex = left;
// 后面没有问题,省略...
}
}
我的疑惑:
为什么在我使用同一种方法,即循环中找答案,在LeetCode 852. 山脉数组的峰顶索引中,不会发生数组下溢的问题呢?
class Solution { public int peakIndexInMountainArray(int[] arr) { int left = 0; int right = arr.length - 1; while(left <= right){ int mid = right + (left - right) / 2; //#修改 if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]){ //刚好命中 return mid; }else if(arr[mid] < arr[mid + 1]){ //在左边 left = mid + 1; }else{ //在右边 right = mid - 1; } } return left; } }
后来仔细一看,噢!我又看走眼了。在这道题我使用的是向上取整,那么mid最小值就为1,从而mid - 1 >= 0
,就不会发生下溢了。
Round 5:大功告成
然后修改成向上取整,大功告成!循环中找答案也没毛病!
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
//Part 1:找到山峰元素索引
int left = 0;
int right = mountainArr.length() - 1;
int topIndex = -1;
while(left <= right){
int mid = right + (left - right) / 2; //right+排除了Mid为0的可能
int midVal = mountainArr.get(mid);
int midMinusVal = mountainArr.get(mid - 1);
int midPlusVal = mountainArr.get(mid + 1);
//刚好命中
if(midMinusVal < midVal && midVal > midPlusVal){
topIndex = mid;
break;
}else if(midVal < midPlusVal){ //mid在左边
left = mid + 1;
}else{ //mid在右边
right = mid - 1;
}
}
}
// 后面没有问题,省略...
}