資訊專欄INFORMATION COLUMN
摘要：給定一個(gè)按照升序排列的整數(shù)數(shù)組，和一個(gè)目標(biāo)值。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。你的算法時(shí)間復(fù)雜度必須是級別。示例輸入輸出示例輸入輸出答案參考
給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。
你的算法時(shí)間復(fù)雜度必須是 O(log n) 級別。
如果數(shù)組中不存在目標(biāo)值，返回 [-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
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/101793.html
摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時(shí)我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場景說說你常用的命令為什么要有包裝類面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時(shí)我在談啥？...
摘要：本文只是簡單理解算法，并不會(huì)深入的討論。大部分來自數(shù)組部分。如果數(shù)組中每個(gè)元素都不相同，則返回。示例輸入輸出加給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。盡量減少操作次數(shù)。 算法（algorithm），在數(shù)學(xué)（算學(xué)）和計(jì)算機(jī)科學(xué)之中，為任何良定義的具體計(jì)算步驟的一個(gè)序列，常用于計(jì)算、數(shù)據(jù)處理和自動(dòng)推理。精確而言，算法是一個(gè)表示為有限長列表的有效方法。算法應(yīng)包含清晰...
摘要：方法返回的數(shù)組元素是調(diào)用的數(shù)組的一個(gè)子集。當(dāng)數(shù)組中至少有一個(gè)元素調(diào)用判定函數(shù)返回，它就返回返回一個(gè)布爾值，當(dāng)有一個(gè)元素符合條件就返回，否則返回和這兩個(gè)方法使用指定的函數(shù)將數(shù)組元素進(jìn)行組合，生成單個(gè)值。 會(huì)改變原數(shù)組的方法： push() 在尾部添加一個(gè)或多個(gè)元素，并返回?cái)?shù)組長度 let arr = [1, 2, 3] arr.push(a, b) // 5 console.log...
摘要：知識(shí)體系梳理流程圖一維數(shù)組數(shù)組概述數(shù)組是指一組數(shù)據(jù)的集合，數(shù)組中的每個(gè)數(shù)據(jù)被稱作元素。定義打印數(shù)組元素方法按照給定的格式打印題目分析通過觀察發(fā)現(xiàn)，要實(shí)現(xiàn)按照指定格式，打印數(shù)組元素操作。按照這種方式，數(shù)組循環(huán)多圈以后，就完成了數(shù)組元素的排序。 知識(shí)體系梳理流程圖 showImg(https://segmentfault.com/img/bVXwAi?w=902&h=652); 一維數(shù)組 ...
閱讀 3729·2021-10-11 10:59
閱讀 1317·2019-08-30 15:44
閱讀 3489·2019-08-29 16:39
閱讀 2897·2019-08-29 16:29
閱讀 1813·2019-08-29 15:24
閱讀 817·2019-08-29 15:05
閱讀 1271·2019-08-29 12:34
閱讀 2351·2019-08-29 12:19
