代码编织梦想

题目

剑指 Offer II 069. 山峰数组的顶部
在这里插入图片描述

思路

虽然整个数组并不是排序的,但分成前后两段后每段都分别排序,因此可以用二分法尝试

如果二分出某个中点mid:

  • rr[mid] > arr[mid-1] && arr[mid] > arr[mid + 1] :mid比左右的元素都大,即找到山峰,直接返回
  • arr[mid] < arr[mid+1] && arr[mid] > arr[mid-1] :mid比右边小,比左边大,说明山峰一定在右边,令l = mid + 1
  • arr[mid] > arr[mid + 1] && arr[mid] < arr[mid-1] :mid比右边小,比左边大,说明山峰一定在左边,令r = mid - 1

代码

public int peakIndexInMountainArray(int[] arr) {
    int l = 0;
    int r = arr.length-1;
    while(l <= r){
        int mid = l + r >> 1;
        if(mid == 0){
            l = mid + 1;
            continue;
        }
        if(mid == arr.length-1){
            r = mid-1;
            continue;
        }


        if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid + 1]){
            return mid;
        }

        if(arr[mid] < arr[mid+1] && arr[mid] > arr[mid-1]){
            l = mid + 1;
        }
        if(arr[mid] > arr[mid + 1] && arr[mid] < arr[mid-1]){
            r = mid - 1;
        } 
    }
    return l;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39383767/article/details/128031743

剑指offer(一):二维数组中的查找_xiaoming3526的博客-爱代码爱编程

剑指Offer(一):二维数组中的查找 搜索微信公众号:‘AI-ming3526’或者’计算机视觉这件小事’ 获取更多算法、机器学习干货 csdn:https://blog.csdn.net/baidu_316578

剑指offer(python)—— 数组中重复的数字(简单)_娱乐不打烊丶的博客-爱代码爱编程

数组中重复的数字 概述:在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 输入:[2, 3, 1, 0, 2, 5, 3] 输出:2 或 3 方法一:暴力循环 思路:容易想到的是先排序后遍历,如果前后值相等,则

2022大厂面试秘籍java岗:中间件+算法+http+线程+虚拟机+分布式_啊码的博客-爱代码爱编程

前言 很多朋友对面试不够了解,不知道如何准备,对面试环节的设置以及目的不够了解,因此成功率不高。通常情况下校招生面试的成功率低于1%,而社招的面试成功率也低于5%,所以对于候选人一定要知道设立面试的初衷以及每个环节的意义,