專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

一網(wǎng)友說(shuō)為什么華子在親戚長(zhǎng)輩面前風(fēng)評(píng)那么好，一聽(tīng)說(shuō)簽了華為都認(rèn)為是年薪百萬(wàn)。在華為年薪百萬(wàn)也不是不可能，但至少要18級(jí)以上。大約7、8年能升到16級(jí)，再往上升就較難。18級(jí)以下占比最多，18級(jí)是個(gè)坎，往上升需要重新考評(píng)，答辯。如果沒(méi)有特殊招聘，一般需要十年以上的時(shí)間才能達(dá)到18級(jí)，也就相當(dāng)于35歲之后了。

--------------下面是今天的算法題--------------

來(lái)看下今天的算法題，這題是LeetCode的第162題：尋找峰值。

問(wèn)題描述

來(lái)源：LeetCode第162題

難度：中等

峰值元素是指其值嚴(yán)格大于左右相鄰值的元素。給你一個(gè)整數(shù)數(shù)組 nums，找到峰值元素并返回其索引。

數(shù)組可能包含多個(gè)峰值，在這種情況下，返回 任何一個(gè)峰值所在位置即可。你可以假設(shè) nums[-1] = nums[n] = -∞ 。

你必須實(shí)現(xiàn)時(shí)間 復(fù)雜度為 O(log n) 的算法 來(lái)解決此問(wèn)題。

示例1：

輸入：nums = [1,2,3,1] 輸出：2 解釋：3 是峰值元素，你的函數(shù)應(yīng)該返回其索引 2。

示例2：

輸入：nums = [1,2,1,3,5,6,4] 輸出：1 或 5 解釋：你的函數(shù)可以返回索引 1，其峰值元素為 2； 或者返回索引 5， 其峰值元素為 6。

• 1 <= nums.length <= 1000

• -2^31 <= nums[i] <= 2^31 - 1

• 對(duì)于所有有效的 i 都有 nums[i] != nums[i + 1]

問(wèn)題分析

這題讓找出數(shù)組中的峰值，因?yàn)閚ums[-1] = nums[n] = -∞ ，也就是默認(rèn)數(shù)組兩邊的值（實(shí)際上是不存在的）是負(fù)無(wú)窮大，所以數(shù)組中肯定是有峰值的。如果沒(méi)有時(shí)間復(fù)雜度的限制，這題就是一道非常簡(jiǎn)單的題，直接遍歷數(shù)組中的每個(gè)值然后與兩邊比較即可。

但這題要求的時(shí)間復(fù)雜度是O(log n) ，所以我們只能使用二分查找，每次用中間的值nums[mid]和它的下一個(gè)值nums[mid+1]比較哪個(gè)大，因?yàn)樘崾局姓f(shuō)了 對(duì)于所有有效的 i 都有 nums[i] != nums[i + 1] ，所以大的那邊一定有峰值。

JAVA：

public int findPeakElement(int[] nums) {     int left = 0;     int right = nums.length - 1;     while (left < right) {         int mid1 = (left + right) >>> 1;         int mid2 = mid1 + 1;         if (nums[mid1] < nums[mid2])             left = mid2;// 右邊肯定有峰值         else             right = mid1;// 左邊肯定有峰值     }     return left; }

C++：

public:     int findPeakElement(vector

 & nums) {         int left = 0;         int right = nums.size() - 1;         while (left < right) {             int mid1 = left +(right-left)/2;             int mid2 = mid1 + 1;             if (nums[mid1] < nums[mid2])                 left = mid2;// 右邊肯定有峰值             else                 right = mid1;// 左邊肯定有峰值         }         return left;     }

Python：

def findPeakElement(self, nums: List[int]) -> int:     left, right = 0, len(nums) - 1     while left < right:         mid1 = left + ((right - left) >> 1)         mid2 = mid1 + 1         if nums[mid1] < nums[mid2]:             left = mid2  # 右邊肯定有峰值         else:             right = mid1  # 左邊肯定有峰值     return left

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫(xiě)算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁(yè)的PDF算法文檔 。