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