写在前面

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

image-20201121200825199

题目

给你一个山脉数组 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]。

来源:LeetCode 1095. 山脉数组中查找目标值

思路

解题思路很简单。

  • 首先找到山脉的山峰元素下标,以此分割左山峰(单调递增)和右山峰(单调递减)
  • 分割完毕后,先对左山峰进行二分查找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;
            }
        }
    }
    
    // 后面没有问题,省略...
}
©著作权归作者所有

发表评论

正在加载 Emoji