给定一个长度为n的非降序排列的整数数组,和一个目标值 。请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 ,返回 [-1, -1]
该题有的解法
[4,7,7,8,8,10],8
[3,4]
可以在数组中找到整数8,其开始位置为3,结束位置为4
[4,7,7,8,8,10],6
[-1,-1]
不可以在数组中找到整数6,故输出整数-1
struct Solution{ } use std::cmp::Ordering::{Less, Equal, Greater}; impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型一维数组 */ pub fn searchRange(&self, nums: Vec<i32>, target: i32) -> Vec<i32> { // write code here vec![ Self::floor(&nums, [-1, nums.len() as i32 - 1], target), Self::ceil(&nums, (-1, nums.len() as i32), target) ] } fn floor(v: &Vec<i32>, [l, r]: [i32; 2], t: i32) -> i32 { // (l, r] if l >= r {return -1} let mid = (l + 1) + (r - l - 1) / 2; // if mid < 0 {} match t.cmp(&v[mid as usize]) { Less => Self::floor(v, [l, mid - 1], t), Greater => Self::floor(v, [mid, r], t), Equal => { let r = Self::floor(v, [l, mid - 1], t); if r == -1 { mid } else {r} } } } fn ceil(v: &Vec<i32>, (l, r): (i32, i32), t: i32) -> i32 { // (l, r) if r - l < 2 { return -1 } let mid = (l + r)/2; match v[mid as usize].cmp(&t) { Greater => Self::ceil(v, (l, mid), t), Less => Self::ceil(v, (mid, r), t), Equal => { let r= Self::ceil(v, (mid, r), t); if r == -1 {mid} else {r} } } } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型vector */ vector<int> searchRange(vector<int>& nums, int target) { // write code here vector<int> v;//作为返回值 if(nums.empty())//判断是否为空 { v.push_back(-1); v.push_back(-1); return v; } int left=0,right=nums.size()-1; int mid; int index=-1; while(left<=right)//二分查找 { mid=(left+right)/2; if(nums[mid]==target) { index=mid; break; } else if(nums[mid]<target) left=mid+1; else right=mid-1; } if(index==-1)//如果查找找不到 { v.push_back(-1); v.push_back(-1); return v; } //找到了 int zuo=index-1; while(zuo>=0&&nums[zuo]==nums[index])//求左区间 { zuo--; } v.push_back(zuo+1); int you=index+1; while(you<nums.size()&&nums[you]==nums[index])//求右区间 { you++; } v.push_back(you-1); return v; } };
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型一维数组 */ function searchRange( nums , target ) { // 用二分法寻找左右侧的边界 let left = findLeftBorder(nums , target); let right = findRightBorder(nums , target); return [left, right]; // 获取左侧边界的函数 function findLeftBorder(nums , target) { let left = 0, right = nums.length - 1; while(left <= right) { let mid = Math.floor(left + (right - left)/2); if(nums[mid] < target) { left = mid + 1; } else if(nums[mid] > target) { right = mid - 1; } else if(nums[mid] === target) { right = mid - 1; } } if(left >= nums.length || nums[left] !== target) { return -1; } else { return left } } // 获取右侧边界的函数 function findRightBorder(nums , target) { let left = 0, right = nums.length - 1; while(left <= right) { let mid = Math.floor(left + (right - left)/2); if(nums[mid] < target) { left = mid + 1; } else if(nums[mid] > target) { right = mid - 1; } else if(nums[mid] === target) { left = mid + 1; } } if(right < 0 || nums[right] !== target) { return -1; } else { return right; } } } module.exports = { searchRange : searchRange };