Find in Mountain Array Solutions in C++
Number 1095
Difficulty Hard
Acceptance 35.8%
Link LeetCode
Other languages —
Solutions
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/find-in-mountain-array//// Author : liuyubobobo/// Time : 2019-06-22#include <iostream>using namespace std;/// Binary Search/// Time Complexity: O(logn)/// Space Complexity: O(logn)class MountainArray {public:int get(int index){return -1;}int length(){return -1;}};class Solution {private:int n;public:int findInMountainArray(int target, MountainArray &mountainArr) {n = mountainArr.length();return findInMountainArray(target, mountainArr, 0, n - 1);}private:int findInMountainArray(int target, MountainArray &mountainArr, int l, int r){if(l > r) return -1;int mid = (l + r) / 2;int e = mountainArr.get(mid);bool isInc = isIncrease(mountainArr, mid, e);if(e == target){if(isInc) return mid;else{int res = findInMountainArray(target, mountainArr, l, mid - 1);return res == -1 ? mid : res;}}else if(e < target){if(isInc) return findInMountainArray(target, mountainArr, mid + 1, r);else return findInMountainArray(target, mountainArr, l, mid - 1);}else{ // e > targetint res = findInMountainArray(target, mountainArr, l, mid - 1);return res == -1 ? findInMountainArray(target, mountainArr, mid + 1, r) : res;}return -1;}bool isIncrease(MountainArray &mountainArr, int index, int e){if(index == 0) return true;int e2 = mountainArr.get(index - 1);return e2 < e;}};int main() {return 0;}
C++ solution by liuyubobobo/Play-Leetcode
/// Source : https://leetcode.com/problems/find-in-mountain-array//// Author : liuyubobobo/// Time : 2019-06-22#include <iostream>using namespace std;/// Find peak and then Using Binary Search/// Time Complexity: O(logn)/// Space Complexity: O(logn)class MountainArray {public:int get(int index){return -1;}int length(){return -1;}};class Solution {private:int n;public:int findInMountainArray(int target, MountainArray &mountainArr) {n = mountainArr.length();// find peakint peak = find_peak(mountainArr);// binary searchint res = binary_search(mountainArr, 0, peak, target, true);return res == -1 ? binary_search(mountainArr, peak, n - 1, target, false) : res;}private:int find_peak(MountainArray &mountainArr){int l = 0, r = n - 1;while(l < r){int mid = (l + r) / 2;if(mountainArr.get(mid) < mountainArr.get(mid + 1))l = mid + 1;elser = mid;}return l;}int binary_search(MountainArray &mountainArr, int l, int r, int target, bool is_inc){while(l <= r){int mid = (l + r) / 2;int e = mountainArr.get(mid);if(e == target) return mid;if(is_inc){if(e < target) l = mid + 1;else r = mid - 1;}else{if(e < target) r = mid - 1;else l = mid + 1;}}return -1;}};int main() {return 0;}