Re: [閒聊] 每日LeetCode已回收
34. Find First and Last Position of Element in Sorted Array
尋找一個Vec的target的左右邊界index
思路：
有序陣列加上題目要求O(log n)
幾乎等於逼你用二元搜尋樹
我建立兩個搜尋樹找左右邊界
往左找跟往右找的差別在於left right mid每次循環往哪邊偏
像往左是let mid = left + (right - left) / 2;
而往右是let mid = left + (right - left + 1) / 2;
往右會讓mid每次+1再/2 會比較靠右 避免無限迴圈TLE
left right也是一樣原理
Code:
impl Solution {
pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
if nums.is_empty() {
return vec![-1, -1];
}
let left = Self::find_left_boundary(&nums, target);
let right = Self::find_right_boundary(&nums, target);
vec![left, right]
}
pub fn find_left_boundary(nums: &Vec<i32>, target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
while left < right {
let mid = left + (right - left) / 2;
if nums[mid] < target {
left = mid + 1;
} else {
right = mid;
}
}
if nums[left] == target {
left as i32
} else {
-1
}
}
pub fn find_right_boundary(nums: &Vec<i32>, target: i32) -> i32 {
let mut left = 0;
let mut right = nums.len() - 1;
while left < right {
let mid = left + (right - left + 1) / 2;
if nums[mid] > target {
right = mid - 1;
} else {
left = mid;
}
}
if nums[left] == target {
left as i32
} else {
-1
}
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.249.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1696862880.A.BAE.html
推
10/09 22:49,
2年前
, 1F
10/09 22:49, 1F
討論串 (同標題文章)
完整討論串 (本文為第 443 之 719 篇)：