您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“C++怎么求數(shù)組的局部峰值”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學(xué)習(xí)“C++怎么求數(shù)組的局部峰值”吧!
這道題是求數(shù)組的一個峰值,如果這里用遍歷整個數(shù)組找最大值肯定會出現(xiàn)Time Limit Exceeded,但題目中說了這個峰值可以是局部的最大值,所以我們只需要找到第一個局部峰值就可以了。所謂峰值就是比周圍兩個數(shù)字都大的數(shù)字,那么只需要跟周圍兩個數(shù)字比較就可以了。既然要跟左右的數(shù)字比較,就得考慮越界的問題,題目中給了nums[-1] = nums[n] = -∞,那么我們其實可以把這兩個整型最小值直接加入到數(shù)組中,然后從第二個數(shù)字遍歷到倒數(shù)第二個數(shù)字,這樣就不會存在越界的可能了。由于題目中說了峰值一定存在,那么有一個很重要的corner case我們要注意,就是當(dāng)原數(shù)組中只有一個數(shù)字,且是整型最小值的時候,我們?nèi)绻€要首尾墊數(shù)字,就會形成一條水平線,從而沒有峰值了,所以我們對于數(shù)組中只有一個數(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; } }
我們可以對上面的線性掃描的方法進行一些優(yōu)化,可以省去首尾墊值的步驟。由于題目中說明了局部峰值一定存在,那么實際上可以從第二個數(shù)字開始往后遍歷,如果第二個數(shù)字比第一個數(shù)字小,說明此時第一個數(shù)字就是一個局部峰值;否則就往后繼續(xù)遍歷,現(xiàn)在是個遞增趨勢,如果此時某個數(shù)字小于前面那個數(shù)字,說明前面數(shù)字就是一個局部峰值,返回位置即可。如果循環(huán)結(jié)束了,說明原數(shù)組是個遞增數(shù)組,返回最后一個位置即可,參見代碼如下:
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; } }
由于題目中提示了要用對數(shù)級的時間復(fù)雜度,那么我們就要考慮使用類似于二分查找法來縮短時間,由于只是需要找到任意一個峰值,那么我們在確定二分查找折半后中間那個元素后,和緊跟的那個元素比較下大小,如果大于,則說明峰值在前面,如果小于則在后面。這樣就可以找到一個峰值了,代碼如下:
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; } }
到此,相信大家對“C++怎么求數(shù)組的局部峰值”有了更深的了解,不妨來實際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。