[LeetCode] 162.Find Peak Element 求數(shù)組的局部峰值

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

Given an input array nums, where nums[i] ≠ nums[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 nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

這道題是求數(shù)組的一個(gè)峰值，如果這里用遍歷整個(gè)數(shù)組找最大值肯定會(huì)出現(xiàn)Time Limit Exceeded，但題目中說了這個(gè)峰值可以是局部的最大值，所以我們只需要找到第一個(gè)局部峰值就可以了。所謂峰值就是比周圍兩個(gè)數(shù)字都大的數(shù)字，那么只需要跟周圍兩個(gè)數(shù)字比較就可以了。既然要跟左右的數(shù)字比較，就得考慮越界的問題，題目中給了nums[-1] = nums[n] = -∞，那么我們其實(shí)可以把這兩個(gè)整型最小值直接加入到數(shù)組中，然后從第二個(gè)數(shù)字遍歷到倒數(shù)第二個(gè)數(shù)字，這樣就不會(huì)存在越界的可能了。由于題目中說了峰值一定存在，那么有一個(gè)很重要的corner case我們要注意，就是當(dāng)原數(shù)組中只有一個(gè)數(shù)字，且是整型最小值的時(shí)候，我們?nèi)绻€要首尾墊數(shù)字，就會(huì)形成一條水平線，從而沒有峰值了，所以我們對(duì)于數(shù)組中只有一個(gè)數(shù)字的情況在開頭直接判斷一下即可，參見代碼如下：

C++ 解法一：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        nums.insert(nums.begin(), INT_MIN);
        nums.push_back(INT_MIN);
        for (int i = 1; i < (int)nums.size() - 1; ++i) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i - 1;
        }
        return -1;
    }
};

Java 解法一：

class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length == 1) return 0;
        int[] newNums = new int[nums.length + 2];
        System.arraycopy(nums, 0, newNums, 1, nums.length);
        newNums[0] = Integer.MIN_VALUE;
        newNums[newNums.length - 1] = Integer.MIN_VALUE;
        for (int i = 1; i < newNums.length - 1; ++i) {
            if (newNums[i] > newNums[i - 1] && newNums[i] > newNums[i + 1]) return i - 1;
        }
        return -1;
    }
}

我們可以對(duì)上面的線性掃描的方法進(jìn)行一些優(yōu)化，可以省去首尾墊值的步驟。由于題目中說明了局部峰值一定存在，那么實(shí)際上可以從第二個(gè)數(shù)字開始往后遍歷，如果第二個(gè)數(shù)字比第一個(gè)數(shù)字小，說明此時(shí)第一個(gè)數(shù)字就是一個(gè)局部峰值；否則就往后繼續(xù)遍歷，現(xiàn)在是個(gè)遞增趨勢(shì)，如果此時(shí)某個(gè)數(shù)字小于前面那個(gè)數(shù)字，說明前面數(shù)字就是一個(gè)局部峰值，返回位置即可。如果循環(huán)結(jié)束了，說明原數(shù)組是個(gè)遞增數(shù)組，返回最后一個(gè)位置即可，參見代碼如下：

C++ 解法二：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < nums[i - 1]) return i - 1;
        }
        return nums.size() - 1;
    }
};

Java 解法二：

public class Solution {
    public int findPeakElement(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] < nums[i - 1]) return i - 1;
        }
        return nums.length - 1;
    }
}

由于題目中提示了要用對(duì)數(shù)級(jí)的時(shí)間復(fù)雜度，那么我們就要考慮使用類似于二分查找法來縮短時(shí)間，由于只是需要找到任意一個(gè)峰值，那么我們?cè)诖_定二分查找折半后中間那個(gè)元素后，和緊跟的那個(gè)元素比較下大小，如果大于，則說明峰值在前面，如果小于則在后面。這樣就可以找到一個(gè)峰值了，代碼如下：

C++ 解法三：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return right;
    }
};

Java 解法三：

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

類似題目：

Peak Index in a Mountain Array

參考資料：

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

https://leetcode.com/problems/find-peak-element/discuss/50232/find-the-maximum-by-binary-search-recursion-and-iteration

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(162.求數(shù)組的局部峰值)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)求數(shù)組的局部峰值內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論