as solution code


  • 0
    /** Solution1. Non-Recusive. time = O(lgN); space = O(1)
         
         Peak Element nums[i]: (greater than its previous/follefting nodes)
         nums[i - 1] < nums[i] > nums[i + 1]
         
         The recursive solution is clearer to show how this method works:
         
         1) Original:  left.....mid1 mid2....right
         
         2) Compare to choose the greater one from mid1/mids:
         if nums[mid1] > nums[mid2], select left...mid1
         if nums[mid1] <= nums[mid2], select mid2...right
         
         3) keep going ..
         
         4) Termination case: left == right, which means we find the element we want
         */
        // Because there's no duplication, so any point only have two possibilities: on upward or downward wave.
        func findPeakElement(_ nums: [Int]) -> Int {
            if nums.count <= 0 {
                return 0
            }
            var mid1 = 0, left = 0, right = nums.count - 1
            while left < right {
                mid1 = (left + right) / 2
                let mid2 = mid1 + 1
                if nums[mid1] > nums[mid2] {//less than previous, on the down wave.
                    right = mid1
                } else if (nums[mid1] < nums[mid2]) {//less than following, on the up wave.
                    left = mid2
                }
            }
            return left
        }
        
        /** Solution2. Recursive. = O(lgN); space = O(n) - system stack
         */
        func findPeakElement_Recursive(_ nums: [Int]) -> Int {
            return helper(nums, 0, nums.count  - 1)
        }
        func helper(_ nums:[Int], _ left: Int, _ right: Int) -> Int {
            if left == right {// Termination case
                return left
            }
            let mid1 = (left + right) / 2
            let mid2 = mid1 + 1
            if nums[mid1] > nums[mid2] {
                return helper(nums, left, mid1)
            } else {
                return helper(nums, mid2, right)
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.