阿里算法面试真题:搜索区间

简介: 阿里算法面试真题:搜索区间

描述
给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中,则返回[-1, -1]

在线评测地址:领扣题库官网

样例1
输入:
[]
9
输出:
[-1,-1]
AI 代码解读
样例2
输入:
[5, 7, 7, 8, 8, 10]
8
输出:
[3, 4]
AI 代码解读

算法:二分
算法思路

  • 由于给定的是一个有序数组,具有单调性,因此很容易想到二分。
  • 二分查找target的第一次出现的位置和最后一次出现的位置,最后输出即可。
  • 具体实现:
  • 对于一个长度为n的升序数组A,二分查找的区间为[0, n - 1],定义left = 0, right = n - 1,中间值mid = left + (right - left) / 2 。
    1. 当 A[mid] > target 时,显然这时查找数值偏大,说明答案在左区间,因此使 right = mid 来缩小查找数值。
    2. 当 A[mid] < target 时,显然这时查找数值偏小,说明答案在右区间,因此使 left = mid 来放大查找数值。
    3. 当 A[mid] == target 时,为了寻找target出现的最左端(第一次出现位置)时,我们选择左区间作为下一次二分区间,因此使 right = mid;为了寻找target出现的最右端(最后一次出现位置)时,我们选择右区间作为下一次二分区间,因此使 left = mid 。
      综上所述:
  • 当我们寻找target的左端点即第一次出现的位置时:
    1. 当 A[mid] < target 时, left = mid ;否则 right = mid。
    2. 最后优先判断并选取接近左边的 left 再判断 right
  • 当我们寻找target的右端点即最后一次出现的位置时:
    1. 当 A[mid] <= target 时, left = mid ;否则 right = mid。
    2. 最后优先判断并选取接近右边的 right 再判断 left
      复杂度分析
  • 常数级别的额外空间,空间复杂度O(1)。
  • 两个二分,时间复杂度O(logn)。

    public class Solution {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    // 寻找左端点
    static int findFirstTargetNum(int[] A, int target, int n){
        int left = 0, right = n - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (A[mid] < target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if (left < n && A[left] == target){
            return left;
        }
        if (right >= 0 && A[right] == target){
            return right;
        }
        return -1;
    }
    
    // 寻找右端点
    static int findLastTargetNum(int[] A, int target, int n){
        int left = 0, right = n - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (A[mid] <= target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if (right >= 0 && A[right] == target){
            return right;
        }
        if (left < n && A[left] == target){
            return left;
        }
        return -1;
    }
    
    public int[] searchRange(int[] A, int target) {
        int n = A.length;
        int[] interval = {-1, -1};
        interval[0] = findFirstTargetNum(A, target, n);
        interval[1] = findLastTargetNum(A, target, n);
        return interval;
    }
    }
    AI 代码解读

    更多题解参考:九章官网solution

目录
打赏
0
0
0
0
6
分享
相关文章
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
121 24
阿里云 AI 搜索开放平台:从算法到业务——AI 搜索驱动企业智能化升级
本文介绍了阿里云 AI 搜索开放平台的技术的特点及其在各行业的应用。
397 3
阿里腾讯互联网公司校招 Java 面试题总结及答案解析
本文总结了阿里巴巴和腾讯等互联网大厂的Java校招面试题及答案,涵盖Java基础、多线程、集合框架、数据库、Spring与MyBatis框架等内容。从数据类型、面向对象特性到异常处理,从线程安全到SQL优化,再到IOC原理与MyBatis结果封装,全面梳理常见考点。通过详细解析,帮助求职者系统掌握Java核心知识,为校招做好充分准备。资源链接:[点击下载](https://pan.quark.cn/s/14fcf913bae6)。
46 2
算法系列之搜索算法-深度优先搜索DFS
深度优先搜索和广度优先搜索一样,都是对图进行搜索的算法,目的也都是从起点开始搜索,直到到达顶点。深度优先搜索会沿着一条路径不断的往下搜索,直到不能够在继续为止,然后在折返,开始搜索下一条候补路径。
219 62
算法系列之搜索算法-深度优先搜索DFS
基于Qlearning强化学习的机器人迷宫路线搜索算法matlab仿真
本内容展示了基于Q-learning算法的机器人迷宫路径搜索仿真及其实现过程。通过Matlab2022a进行仿真,结果以图形形式呈现,无水印(附图1-4)。算法理论部分介绍了Q-learning的核心概念,包括智能体、环境、状态、动作和奖励,以及Q表的构建与更新方法。具体实现中,将迷宫抽象为二维网格世界,定义起点和终点,利用Q-learning训练机器人找到最优路径。核心程序代码实现了多轮训练、累计奖励值与Q值的可视化,并展示了机器人从起点到终点的路径规划过程。
72 0
阿里面试:Redis 为啥那么快?怎么实现的100W并发?说出了6大架构,面试官跪地: 纯内存 + 尖端结构 + 无锁架构 + EDA架构 + 异步日志 + 集群架构
阿里面试:Redis 为啥那么快?怎么实现的100W并发?说出了6大架构,面试官跪地: 纯内存 + 尖端结构 + 无锁架构 + EDA架构 + 异步日志 + 集群架构
阿里面试:Redis 为啥那么快?怎么实现的100W并发?说出了6大架构,面试官跪地: 纯内存 + 尖端结构 +  无锁架构 +  EDA架构  + 异步日志 + 集群架构
阿里面试:PS+PO、CMS、G1、ZGC区别在哪?什么是卡表、记忆集、联合表?问懵了,尼恩来一个 图解+秒懂+史上最全的答案
阿里面试:PS+PO、CMS、G1、ZGC区别在哪?什么是卡表、记忆集、联合表?问懵了,尼恩来一个 图解+秒懂+史上最全的答案
阿里面试:每天新增100w订单,如何的分库分表?这份答案让我当场拿了offer
例如,在一个有 10 个节点的系统中,增加一个新节点,只会影响到该新节点在哈希环上相邻的部分数据,其他大部分数据仍然可以保持在原节点,大大减少了数据迁移的工作量和对系统的影响。狠狠卷,实现 “offer自由” 很容易的, 前段时间一个武汉的跟着尼恩卷了2年的小伙伴, 在极度严寒/痛苦被裁的环境下, offer拿到手软, 实现真正的 “offer自由”。在 3 - 5 年的中期阶段,随着业务的稳定发展和市场份额的进一步扩大,订单数据的增长速度可能会有所放缓,但仍然会保持在每年 20% - 30% 的水平。
阿里面试:每天新增100w订单,如何的分库分表?这份答案让我当场拿了offer
|
5月前
|
算法系列之搜索算法-广度优先搜索BFS
广度优先搜索(BFS)是一种非常强大的算法,特别适用于解决最短路径、层次遍历和连通性问题。在面试中,掌握BFS的基本实现和应用场景,能够帮助你高效解决许多与图或树相关的问题。
224 1
算法系列之搜索算法-广度优先搜索BFS

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问