LeetCode34.在排序数组中查找元素的第一个和最后一个位置 JavaScript

Pines_Cheng 发布于2019-08-23 15:16 / 734人阅读

摘要：给定一个按照升序排列的整数数组，和一个目标值。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是级别。示例输入输出示例输入输出答案参考

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

答案参考：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
    let targetIndex = binarySearch(nums, target, 0, nums.length - 1)
    if (targetIndex == -1) return [-1, -1]
    let l = targetIndex, r = targetIndex
    while(l > 0 && nums[l - 1] == target){
        l--
    }
    while(r < nums.length - 1 && nums[r + 1] == target){
        r++
    }
    return [l, r]
};

function binarySearch(arr, val, lo, hi) {
    if (hi < lo) return -1
    let mid = lo + parseInt((hi - lo) / 2)

    if (val < arr[mid]) {
        return binarySearch(arr, val, lo, mid - 1)
    } else if (val > arr[mid]) {
        return binarySearch(arr, val, mid + 1, hi)
    } else {
        return mid
    }
}

服务器托管私有云找出一个二维数组中的鞍点总是最后一个最后一个值在一个c语言程序中

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101793.html

6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
TypeScript实现数组相关简单算法

摘要：本文只是简单理解算法，并不会深入的讨论。大部分来自数组部分。如果数组中每个元素都不相同，则返回。示例输入输出加给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。尽量减少操作次数。算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰...

cloud 2019-08-23 11:55 评论0 收藏0
数组七十二变

摘要：方法返回的数组元素是调用的数组的一个子集。当数组中至少有一个元素调用判定函数返回，它就返回返回一个布尔值，当有一个元素符合条件就返回，否则返回和这两个方法使用指定的函数将数组元素进行组合，生成单个值。会改变原数组的方法： push() 在尾部添加一个或多个元素，并返回数组长度 let arr = [1, 2, 3] arr.push(a, b) // 5 console.log...

alexnevsky 2019-08-23 10:54 评论0 收藏0
java知识体系梳理-->数组

摘要：知识体系梳理流程图一维数组数组概述数组是指一组数据的集合，数组中的每个数据被称作元素。定义打印数组元素方法按照给定的格式打印题目分析通过观察发现，要实现按照指定格式，打印数组元素操作。按照这种方式，数组循环多圈以后，就完成了数组元素的排序。知识体系梳理流程图 showImg(https://segmentfault.com/img/bVXwAi?w=902&h=652); 一维数组 ...

james 2019-08-15 12:23 评论0 收藏0