二分 & 三分查值问题

简介: 二分 & 三分查值问题

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 852. 山脉数组的峰顶索引 ,难度为 简单


Tag : 「二分」、「三分」


符合下列属性的数组 arr 称为 山脉数组 :


  • arr.length >= 3
  • 存在i(0 < i < arr.length - 1)使得:
  • arr[0] < arr[1] < ... arr[i-1] < arr[i]
  • arr[i] > arr[i+1] > ... > arr[arr.length - 1]


给你由整数组成的山脉数组 arr ,返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i


示例 1:


输入:arr = [0,1,0]
输出:1
复制代码


示例 2:


输入:arr = [0,2,1,0]
输出:1
复制代码


示例 3:


输入:arr = [0,10,5,2]
输出:1
复制代码


示例 4:


输入:arr = [3,4,5,1]
输出:2
复制代码


示例 5:


输入:arr = [24,69,100,99,79,78,67,36,26,19]
输出:2
复制代码


提示:


  • 3 <= arr.length <= 10^4104
  • 0 <= arr[i] <= 10^6106
  • 题目数据保证 arr 是一个山脉数组


进阶:很容易想到时间复杂度 O(n) 的解决方案,你可以设计一个 O(log(n)) 的解决方案吗?


二分



往常我们使用「二分」进行查值,需要确保序列本身满足「二段性」:当选定一个端点(基准值)后,结合「一段满足 & 另一段不满足」的特性来实现“折半”的查找效果。


但本题求的是峰顶索引值,如果我们选定数组头部或者尾部元素,其实无法根据大小关系“直接”将数组分成两段。


但可以利用题目发现如下性质:由于 arr 数值各不相同,因此峰顶元素左侧必然满足严格单调递增,峰顶元素右侧必然不满足。


因此 以峰顶元素为分割点的 arr 数组,根据与 前一元素/后一元素 的大小关系,具有二段性:


  • 峰顶元素左侧满足 arr[i-1] < arr[i]arr[i1]<arr[i] 性质,右侧不满足
  • 峰顶元素右侧满足 arr[i] > arr[i+1]arr[i]>arr[i+1] 性质,左侧不满足


因此我们可以选择任意条件,写出若干「二分」版本。


代码:


class Solution {
    // 根据 arr[i-1] < arr[i] 在 [1,n-1] 范围内找值
    // 峰顶元素为符合条件的最靠近中心的元素
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid - 1] < arr[mid]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
}
复制代码


class Solution {
    // 根据 arr[i] > arr[i+1] 在 [0,n-2] 范围内找值
    // 峰顶元素为符合条件的最靠近中心的元素值
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 2;
        while (l < r) {
            int mid = l + r >> 1;
            if (arr[mid] > arr[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}
复制代码


class Solution {
    // 根据 arr[i-1] > arr[i] 在 [1,n-1] 范围内找值
    // 峰顶元素为符合条件的最靠近中心的元素的前一个值
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (arr[mid - 1] > arr[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r - 1;
    }
}
复制代码


class Solution {
    // 根据 arr[i] < arr[i+1] 在 [0,n-2] 范围内找值
    // 峰顶元素为符合条件的最靠近中心的元素的下一个值
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 2;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid] < arr[mid + 1]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r + 1;
    }
}
复制代码


  • 时间复杂度:O(\log{n})O(logn)
  • 空间复杂度:O(1)O(1)


三分



事实上,我们还可以利用「三分」来解决这个问题。


顾名思义,「三分」就是使用两个端点将区间分成三份,然后通过每次否决三分之一的区间来逼近目标值。


具体的,由于峰顶元素为全局最大值,因此我们可以每次将当前区间分为 [l, m1][l,m1][m1, m2][m1,m2][m2, r][m2,r] 三段,如果满足 arr[m1] > arr[m2]arr[m1]>arr[m2],说明峰顶元素不可能存在与 [m2, r][m2,r] 中,让 r = m2 - 1r=m21 即可。另外一个区间分析同理。


代码:


class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;
            if (arr[m1] > arr[m2]) {
                r = m2 - 1;
            } else {
                l = m1 + 1;
            }
        }
        return r;
    }
}
复制代码


  • 时间复杂度:O(\log_3{n})O(log3n)
  • 空间复杂度:O(1)O(1)


其他「二分」相关题解




最后



这是我们「刷穿 LeetCode」系列文章的第 No.852 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
JavaScript 前端开发 C++
CocosCreator3.8研究笔记(六)CocosCreator 脚本装饰器的理解
CocosCreator3.8研究笔记(六)CocosCreator 脚本装饰器的理解
386 0
|
机器学习/深度学习 存储 自然语言处理
让大模型的训练和推理,比更快还更快!谷歌2022年终总结第四弹(2)
让大模型的训练和推理,比更快还更快!谷歌2022年终总结第四弹
303 0
|
机器人
机器人程序设计_ROS_note2
本笔记关于ROS文件系统认识以及常用命令的实践 环境:ubuntu16.04 & ROS-Ubuntu2 0.安装tree: 1.
855 0
|
10天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
9天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
404 130
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
3天前
|
存储 安全 前端开发
如何将加密和解密函数应用到实际项目中?
如何将加密和解密函数应用到实际项目中?
197 138