162.find-peak-element.md

問題

https://leetcode.com/problems/find-peak-element/

回答

初回の回答:

二分探索をして、両隣より大きいかどうかを判定していく。最初は左半分、見つからなかったら右半分という順番で行う。しかし、中央付近にピークがある場合に見つけることができず、この実装はパスしなかった。しかもかなり複雑な条件分岐になってしまった。

impl Solution {
    pub fn find_peak_element(nums: Vec<i32>) -> i32 {
        if nums.len() == 1 {
            return 0;
        }

        if nums.len() == 2 {
            if nums[0] > nums[1] {
                return 0;
            } else {
                return 1;
            }
        }

        let mut result = -1;
        let mut l = 0;
        let mut r = nums.len() - 1;
        while l < r {
            let m = l + (r - l) / 2;
            if m == 0 {
                if nums[m] > nums[m + 1] {
                    result = m as i32;
                }
                break;
            }
            if nums[m - 1] < nums[m] && nums[m] > nums[m + 1] {
                result = m as i32;
                break;
            } else {
                r = m;
            }
        }
        if result >= 0 {
            return result;
        }

        r = nums.len() - 1;
        l = l + (r - l) / 2;
        while l <= r {
            let m = l + (r - l) / 2;
            if m == nums.len() - 1 {
                if nums[m - 1] < nums[m] {
                    result = m as i32;
                }
                break;
            }
            if nums[m - 1] < nums[m] && nums[m] > nums[m + 1] {
                result = m as i32;
                break;
            } else {
                l = m + 1;
            }
        }
        result
    }
}

二回目の回答:

両隣が自身より小さい要素を見つけるという問題から条件をつくるとすると、

• $nums[m] < nums[m+1]$ の場合、少なくとも１つは $nums[m+1]$ 側にピークが存在する。
• $nums[m] > nums[m+1]$ の場合、自身がピークである可能性はある。

右隣を考えるか左隣を考えるかは特に差はなく、イメージ的にはとにかく上を目指すという感じ。最初は理解できなかったけど、上記のように条件を書き下してみると納得した。

※ ちなみに MIT の授業で Peak Finding について解説している YouTube がある。https://youtu.be/HtSuA80QTyo?t=1645

impl Solution {
    pub fn find_peak_element(nums: Vec<i32>) -> i32 {
        let mut l = 0;
        let mut r = nums.len() - 1;
        while l < r {
            let m = l + (r - l) / 2;
            if nums[m] > nums[m + 1] {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l as i32
   }
}