【剑指Offer】--->详解二分查找相关练习(二)

简介: 【剑指Offer】--->详解二分查找相关练习(二)

3 寻找峰值

题目描述;

给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗?

数据范围:

1≤nums.length≤2×10^5

−2^31<=nums[i]<=2^31−1

如输入[2,4,1,2,7,8,4]时,会形成两个山峰,一个是索引为1,峰值为4的山峰,另一个是索引为5,峰值为8的山峰,如下图所示:

8807de221e414f9281741964df6b07a9.png

示例1:

输入:[2,4,1,2,7,8,4]

返回值:1

说明:4和8都是峰值元素,返回4的索引1或者8的索引5都可以

示例2:

输入:[1,2,3,1]

返回值:2

说明:3 是峰值元素,返回其索引 2

解题思路:

题目要求时间复杂度为O(logN),所以暴力求解肯定不行,因为题目将数组边界看成最小值,而我们只需要找到其中一个波峰,因此只要不断地往高处走,一定会有波峰。那我们可以每次找一个标杆元素,将数组分成两个区间,每次就较高的一边走,因此也可以用分治来解决,而标杆元素可以选择区间中点。

如果中间值大于它右边的值:我们不妨举个例子[x,x,x,5,4,x,x],其中x为任意值,我们可以带入一些值进去发现右边是不一定有坡峰的,如[x,x,x,5,4,5,4](有坡峰)[x,x,x,5,4,3,2](无坡峰),这也好解释由于右边是往下走的所以不能够确定峰值。但是左边一定是会有峰值的,同理我们可以来分析如果左边值是逐渐递减的如[9,8,6,5,4,x,x],我们可以知道9就是峰值,如果索引为2的值只要小于5那么5就是峰值,如果索引为2的值大于5那么索引为1的值如果小于索引为2的话索引为2就是峰值,否则索引为0的值如果大于索引为1的话索引为0就是峰值,否则索引为1的就是峰值。(这里关系比较复杂,大家可以自己去推推)。

同理如果中间值小于右边的元素,说明此时往右是向上,向上一定能有波峰。

动图展示:


766198e6e9d34f77b5411b0cdb711f2d.gif

具体代码:

int findPeakElement(int* nums, int numsLen ) {
    // write code here
    int left=0;
    int right=numsLen-1;
    while(left<right)
    {
        int mid=(left+right)/2;
        if(nums[mid]>nums[mid+1])
        {
            right=mid;
        }
        else
        {
            left=mid+1;
        }
    }
    return left;
}

注意事项:

  1. while循环中没有加=,加了=后会出错
  2. 往高处走一定有坡峰,当nums[mid]>nums[mid+1]时,中间值更大,所以向左缩短区间,nums[mid]<nums[mid+1]时,中间值右边更大,所以向右缩短区间。

4 二维数组的查找

题目描述:

在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

[

[1,2,8,9],

[2,4,9,12],

[4,7,10,13],

[6,8,11,15]

]

给定 target = 7,返回 true。

给定 target = 3,返回 false。

数据范围:矩阵的长宽满足 0≤n,m≤5000, 矩阵中的值满足 0≤val≤10^9

进阶:空间复杂度 O(1),时间复杂度 O(n+m)

示例1:

输入:7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值:true

说明:存在7,返回true

示例2:

输入:1,[[2]]

返回值:false

说明:不存在1,返回false

示例3:

输入:3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值:false

说明:不存在3,返回false

解题思路:

这道题常规遍历肯定是行不通的,我们可以考虑用二分查找的思维来做题,二分查找就是不断的缩小区间直至我们找到我们想要找到的数据,我们通过题目描述不难发现这个二维数组其实就是一个杨氏矩阵(行从左到右依次递增,列从上到下依次递增),我们可以紧紧抓住这个条件,首先将数据定位到最右上边的元素(左下也行),如果要查找的元素比右上边的元素还大,那我们就可以排除这一行了,如果要查找的元素比右上边的元素还小,那么就可以排除这一列,然后迭代的走下去,注意控制循环结束的条件。

动图展示:

0ba4517245c941a2840ac5adb6caa701.gif

具体代码:

bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int row=0;
    int col=*arrayColLen-1;
    while(row < arrayRowLen  && col >= 0)
    {
        if(array[row][col] > target)
        {
            col--;
        }
        else if(array[row][col] < target)
        {
            row++;
        }
        else 
        {
            return true;
        }
    }
    return false;
}

注意事项:

循环结束的条件要控制好。

结语

与二分查找相关的题目还有很多,但是终归这些题都是在如何利用已知条件来转换成我们所熟悉的二分方法,如果觉得博主的文章对你有帮助的话可不可以3连支持一下,后面博主还会持续更新剑指offer上的有关题目。

目录
相关文章
|
存储 缓存 Java
【并发编程的艺术】详解指令重排序与数据依赖
本章详细描述了指令重排序的场景,条件,以及数据依赖、控制依赖对指令重排序的影响。总结如下: 单线程程序,对存在控制依赖的操作执行重排序,不会改变执行结果;但在多线程程序中,对存在控制依赖的操作执行重排序,可能会改变程序的执行结果!这就是多线程执行时出现并发问题的根本原因,切记。
295 0
|
Java
JVM之本地内存以及元空间,直接内存的详细解析
JVM之本地内存以及元空间,直接内存的详细解析
1056 0
|
Linux Docker 容器
阿里云安装Docker 步骤
阿里云安装Docker 步骤: step 1: 安装必要的一些系统工具 sudo yum install -y yum-utils device-mapper-persistent-data lvm2 Step 2: 添加软件源信息 sudo yum-config-manager --add-repo http://mirrors.
4617 0
|
8月前
|
监控 安全 物联网
工厂人员定位管理系统方案:实现低成本高精度人员定位
蓝牙定位技术结合Lora技术,实现低成本、高效率的工厂人员定位管理,能够提升生产效率、保障安全、优化应急响应的关键工具。该系统能够实时获取工厂内人员的位置信息,为生产调度、安全监控、紧急疏散等提供精确、及时的数据支持。
350 5
|
Web App开发 API 图形学
QtWebEngine性能问题
QtWebEngine性能问题
515 1
|
机器学习/深度学习 算法 定位技术
Python实现SMOGN算法解决不平衡数据的回归问题
Python实现SMOGN算法解决不平衡数据的回归问题
202 1
|
存储 NoSQL Shell
redis string底层数据结构
redis数据存储结构  redis的内部整体的存储结构就是一个大的hashmap,内部实现是数组实现hash,冲突通过挂链去实现,然后每个dictEntry就是一个key/value对象。
2386 0
|
算法 异构计算
m基于FPGA的4ASK调制解调系统verilog实现,包含testbench测试文件
m基于FPGA的4ASK调制解调系统verilog实现,包含testbench测试文件
242 0
|
SpringCloudAlibaba Java Nacos
「Spring Cloud Alibaba官方手册」首发爆火,Github上标星243k
几年前 Dubbo被 SpringCloud所取代,相同的剧本,可惜阿里巴巴和 Spring社区都是巨头,巨头之间战斗要考虑很多,于是它们想到了合作, SpringCloud与alibaba相结合,技术上有人负责更新新的组件,也还可以继续使用 Spring社区的技术。于是 SpringCloudAlibaba诞生了。
204 0
|
算法 编译器 C语言
【C++技能树】类和对象的使用 --初始化列表,static,友元,内部类,匿名对象的理解与使用
虽然我们大多时候混淆初始化与赋值的概念,但在这里,构造函数体中只能成为赋值,因为初始化只能初始化一次,而赋值可以赋值多次。那么在哪里进行初始化呢?可能会说在定义时直接初始化,这在日期类中是可以的,但在这种情况当中,显然是不可以的了
125 0