C++實現(xiàn)LeetCode(162.求數組的局部峰值)
[LeetCode] 162.Find Peak Element 求數組的局部峰值
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.
這道題是求數組的一個峰值，如果這里用遍歷整個數組找最大值肯定會出現(xiàn)Time Limit Exceeded，但題目中說了這個峰值可以是局部的最大值，所以我們只需要找到第一個局部峰值就可以了。所謂峰值就是比周圍兩個數字都大的數字，那么只需要跟周圍兩個數字比較就可以了。既然要跟左右的數字比較，就得考慮越界的問題，題目中給了nums[-1] = nums[n] = -∞，那么我們其實可以把這兩個整型最小值直接加入到數組中，然后從第二個數字遍歷到倒數第二個數字，這樣就不會存在越界的可能了。由于題目中說了峰值一定存在，那么有一個很重要的corner case我們要注意，就是當原數組中只有一個數字，且是整型最小值的時候，我們如果還要首尾墊數字，就會形成一條水平線，從而沒有峰值了，所以我們對于數組中只有一個數字的情況在開頭直接判斷一下即可，參見代碼如下：
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;
}
}
我們可以對上面的線性掃描的方法進行一些優(yōu)化，可以省去首尾墊值的步驟。由于題目中說明了局部峰值一定存在，那么實際上可以從第二個數字開始往后遍歷，如果第二個數字比第一個數字小，說明此時第一個數字就是一個局部峰值；否則就往后繼續(xù)遍歷，現(xiàn)在是個遞增趨勢，如果此時某個數字小于前面那個數字，說明前面數字就是一個局部峰值，返回位置即可。如果循環(huán)結束了，說明原數組是個遞增數組，返回最后一個位置即可，參見代碼如下：
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;
}
}
由于題目中提示了要用對數級的時間復雜度，那么我們就要考慮使用類似于二分查找法來縮短時間，由于只是需要找到任意一個峰值，那么我們在確定二分查找折半后中間那個元素后，和緊跟的那個元素比較下大小，如果大于，則說明峰值在前面，如果小于則在后面。這樣就可以找到一個峰值了，代碼如下：
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
到此這篇關于C++實現(xiàn)LeetCode(162.求數組的局部峰值)的文章就介紹到這了,更多相關C++實現(xiàn)求數組的局部峰值內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文主要介紹了QT中進程的創(chuàng)建實現(xiàn),詳細介紹了創(chuàng)建進程的整個過程,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2023-08-08
這篇文章主要介紹了設計模式中的模板方法模式及在C++中的使用,模板方法將邏輯封裝到一個類中,并采取組合(委托)的方式解決這個問題,需要的朋友可以參考下2016-03-03
這篇文章主要為大家詳細介紹了C語言實現(xiàn)隨機抽取紙牌程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
C語言函數是用來模塊化構建程序的。如果你的功能少，你可以全都寫在mian函數中，但是當實現(xiàn)功能多的時候，如果全寫在main的函數里，不僅代碼不美觀，而且函數實現(xiàn)的時候結構復雜，代碼重復2022-05-05
這篇文章主要介紹了C++如何計算二進制數中1的個數，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
柔性數組是在C99中定義的，即結構體的最后一個元素允許是未知大小的數組，這就叫柔性數組。這篇文章將通過簡單的示例為大家介紹一下柔性數組的使用，感興趣的可以了解一下2023-02-02
C語言詳盡圖解函數棧幀的創(chuàng)建和銷毀實現(xiàn)
我們知道c語言中函數都是被調用的，main函數里面能調用其他函數，其實main函數也是被別的函數調用的，下面通過本文給大家分享c語言函數棧幀的創(chuàng)建和銷毀過程，一起看看吧2022-05-05
這篇文章主要介紹了C語言查找數組里數字重復次數的方法,涉及C語言針對數組的遍歷與判斷技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
do...while(0)消除goto語句；通常，如果在一個函數中開始要分配一些資源，然后在中途執(zhí)行過程中如果遇到錯誤則退出函數，當然，退出前先釋放資源2013-09-09
這篇文章主要介紹了C語言中printf輸出的相關函數總結,是C語言入門學習中的基礎知識,需要的朋友可以參考下2015-08-08