Re: [閒聊] 每日LeetCode

[yam276 (史萊哲林的優等生)]

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
推 Rushia: 大師