Peak Index in a Mountain Array Solutions in C++
Number 852
Difficulty Easy
Acceptance 71.6%
Link LeetCode
Other languages Go
Solutions
C++ solution by haoel/leetcode
// Source : https://leetcode.com/problems/peak-index-in-a-mountain-array/description/// Author : Hao Chen// Date : 2018-06-29class Solution {public:int peakIndexInMountainArray(vector<int>& A) {// Put two dummy items at head and tail to avoid Out-of-Bound Error.#define INT_MAX 2147483647#define INT_MIN (-INT_MAX - 1)A.insert ( A.begin() , INT_MIN );A.push_back(INT_MIN);//binary searchint len = A.size();int left = 1, right = len - 2;while(left <= right) {int mid = left + (right - left)/2; //avoid integer overflowif ( A[mid-1] < A[mid] && A[mid] > A[mid+1]) return mid-1;if ( A[mid-1] < A[mid] && A[mid] < A[mid+1]) left = mid + 1;if ( A[mid-1] > A[mid] && A[mid] > A[mid+1]) right = mid - 1;}return -1;}};
C++ solution by liuyubobobo/Play-Leetcode
/// https://leetcode.com/problems/peak-index-in-a-mountain-array/description//// Author : liuyubobobo/// Time : 2018-06-17#include <iostream>#include <vector>#include <cassert>using namespace std;/// Two Linear Scans/// Time Complexity: O(n)/// Space Complexity: O(1)class Solution {public:int peakIndexInMountainArray(vector<int>& A) {int maxValue = A[0];for(int a: A)maxValue = max(maxValue, a);for(int i = 0 ; i < A.size() ; i ++)if(A[i] == maxValue)return i;assert(false);return -1;}};int main() {vector<int> nums1 = {0, 1, 0};cout << Solution().peakIndexInMountainArray(nums1) << endl;vector<int> nums2 = {0, 2, 1, 0};cout << Solution().peakIndexInMountainArray(nums2) << endl;return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// https://leetcode.com/problems/peak-index-in-a-mountain-array/description//// Author : liuyubobobo/// Time : 2018-06-16#include <iostream>#include <vector>using namespace std;/// One Linear Scan/// Time Complexity: O(n)/// Space Complexity: O(1)class Solution {public:int peakIndexInMountainArray(vector<int>& A) {for(int i = 1 ; i < A.size() ; i ++)if(A[i - 1] > A[i])return i - 1;return A.size() - 1;}};int main() {vector<int> nums1 = {0, 1, 0};cout << Solution().peakIndexInMountainArray(nums1) << endl;vector<int> nums2 = {0, 2, 1, 0};cout << Solution().peakIndexInMountainArray(nums2) << endl;return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// https://leetcode.com/problems/peak-index-in-a-mountain-array/description//// Author : liuyubobobo/// Time : 2018-06-17#include <iostream>#include <vector>using namespace std;/// Binary Search/// Make an array of [True, True, ... , True, False, False, ... , False]/// Find the largest index which is True////// Time Complexity: O(logn)/// Space Complexity: O(n)class Solution {public:int peakIndexInMountainArray(vector<int>& A) {vector<bool> vec;for(int i = 1 ; i < A.size() ; i ++)vec.push_back(A[i-1] < A[i]);int l = 0, r = vec.size() - 1;while(l < r){int mid = (l + r + 1) / 2;if(vec[mid])l = mid;elser = mid - 1;}return l + 1;}};int main() {vector<int> nums1 = {0, 1, 0};cout << Solution().peakIndexInMountainArray(nums1) << endl;vector<int> nums2 = {0, 2, 1, 0};cout << Solution().peakIndexInMountainArray(nums2) << endl;return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// https://leetcode.com/problems/peak-index-in-a-mountain-array/description//// Author : liuyubobobo/// Time : 2018-06-17#include <iostream>#include <vector>using namespace std;/// Binary Search in A directly/// Time Complexity: O(logn)/// Space Complexity: O(n)class Solution {public:int peakIndexInMountainArray(vector<int>& A) {int l = 0, r = A.size() - 1;while(l < r){int mid = (l + r + 1) / 2;if(A[mid - 1] < A[mid])l = mid;elser = mid - 1;}return l;}};int main() {vector<int> nums1 = {0, 1, 0};cout << Solution().peakIndexInMountainArray(nums1) << endl;vector<int> nums2 = {0, 2, 1, 0};cout << Solution().peakIndexInMountainArray(nums2) << endl;return 0;}