LeetCode：Find Peak Element - 尋找一個數組内的頂點

1、題目名稱

Find Peak Element（尋找一個數組内的頂點）

2、題目位址

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

3、題目内容

英文：

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

中文：

在一個數組内，如果某元素比它左右兩個元素都大，則稱該元素為一個“頂點”。現給出一個相鄰元素一定不相同的數組，找出一個頂點元素并傳回它的索引。一個數組中可能包含多個頂點，在這種情況下傳回任意一個頂點的坐标即可。你可以假定第-1個元素和第n個元素是負無窮（這句話的意思就是最左邊的元素假定它“再左邊”還有一個比它小的元素，最右邊的元素同理）。

例如：給定數組 [1, 2, 3, 1]，則元素3是一個頂點，應傳回它的索引值2

4、解題方法1

最容易想到的辦法自然是自左至右周遊數組，如果某元素比它左邊和右邊的元素大，則該元素必為頂點。傳回找到的第一個頂點即可。

Java代碼如下：

/**
 * @功能說明：LeetCode 162 - Find Peak Element
 * @開發人員：Tsybius2014
 * @開發時間：2015年11月4日
 */
public class Solution {
    
    /**
     * 尋找頂點
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {
        
        if (nums == null) {
            return -1;
        } else if (nums.length == 0) {
            return -1;
        } else if (nums.length == 1) {
            return 0;
        } else if (nums[0] > nums[1]) {
            return 0;
        } else if (nums[nums.length - 1] > nums[nums.length - 2]) {
            return nums.length - 1;
        }
        
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i - 1] <= nums[i] && nums[i + 1] <= nums[i]) {
                return i;
            }
        }
        
        return -1;
    }
}
           

4、解題方法2

另一種方法是使用二分查找法解決問題。這個方法利用了題目中的如下性質：

1）最左邊的元素，它“更左邊”的元素比它小（負無窮），我們認為它是一個增長的方向

2）最右邊的元素，它“更右邊”的元素比它小（也是負無窮），我們認為它是一個下降的方向

根據這兩點我們可以判斷：最左邊和最右邊的元素圍成的區域内，必有至少一個頂點

現在我們找到中點 nums[mid]，将它與 nums[mid + 1] 作比較，如果前者較小，則方向是增長，與最左邊的元素是一緻的，就把左邊界挪到mid+1的位置；否則與最右邊的元素一緻，将右邊界挪到mid的位置。

這個方法的原理就是當左邊界方向為“增長”，右邊界方向為“下降”時，二者圍出的區域必有一個頂點。我們可以寫出如下Java代碼實作此方法：

/**
 * @功能說明：LeetCode 162 - Find Peak Element
 * @開發人員：Tsybius2014
 * @開發時間：2015年11月4日
 */
public class Solution {
    
    /**
     * 尋找頂點
     * @param nums
     * @return
     */
    public int findPeakElement(int[] nums) {
        
        if (nums == null) {
            return -1;
        } else if (nums.length == 0) {
            return -1;
        } else if (nums.length == 1) {
            return 0;
        } 

        int left = 0;
        int mid = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}
           

本題也可以使用遞歸的方式進行二分搜尋。

END

轉載于:https://my.oschina.net/Tsybius2014/blog/526016