forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 39
/
findPeakElement.cpp
141 lines (110 loc) · 3.23 KB
/
findPeakElement.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
// Source : https://oj.leetcode.com/problems/find-peak-element/
// Author : Hao Chen
// Date : 2014-12-05
/**********************************************************************************
*
* A peak element is an element that is greater than its neighbors.
*
* Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
*
* You may imagine that num[-1] = num[n] = -∞.
*
* For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
*
* click to show spoilers.
*
* Note:
* Your solution should be in logarithmic complexity.
*
* Credits:Special thanks to @ts for adding this problem and creating all test cases.
*
**********************************************************************************/
#include <iostream>
#include <vector>
using namespace std;
/*
* Binary search is common idea here.
*
* However, you need to think about two senarios:
*
* 1) Becasue we need check `num[mid-1]`, `num[mid]`, `num[mid+1]`,
* So, we need make sure there hasn't out-of-boundary issue.
*
*
*
* 2) There are multiple Peak elements.
*
* For example: [1,2,1,2,1], or [ 1,2,3,1,2,1]
*
* LeetCode doesn't tell you what the expected result is. I guess:
*
* 2.1) for [1,2,1,2,1] you can return either 1 or 3, because both them are peak elements
*
* 2.1) for [1,2,3,2,4,2,1] it should return 4, because num[4] is the real peak. but Leetcode accept either 2 or 4
*
*/
int findPeakElement(const vector<int> &num) {
int n = num.size();
int low = 0;
int high = n - 1;
int mid = 0, v1, v2;
while ( low < high ) {
// Find the index of middle element
mid = low + ( high - low ) / 2;
// Compare middle element with its neighbours (if neighbours exist)
if ( ( mid == 0 || num[mid] > num[mid-1] ) &&
( mid == n-1 || num[mid] > num[mid+1] ) ){
return mid;
}
// If middle element is not peak and its left neighbor is greater than it
// then left half must have a peak element
if (mid >0 && num[mid-1] > num[mid]){
high = mid - 1;
// If middle element is not peak and its right neighbor is greater than it
// then right half must have a peak element
}else{
low = mid + 1;
}
}
return low;
}
void printVector(vector<int> &n) {
cout << "[ ";
int i;
for(i=0; i<n.size(); i++){
cout << n[i] << (i==n.size()-1 ? " ]" : ", ");
}
cout << endl;
}
void test(int a[], int n) {
vector<int> v(a, a+n);
cout << "Peak Index = " << findPeakElement(v) << "\t";
printVector(v);
}
#define TEST(a) test(a, sizeof(a)/sizeof(a[0]))
int main(int argc, char**argv)
{
int n0[] = {1};
TEST(n0);
int n1[] = {1,2};
TEST(n1);
int n2[] = {2,1};
TEST(n2);
int n3[] = {1,2,3};
TEST(n3);
int n4[] = {3,2,1};
TEST(n4);
int n5[] = {1,2,3,2};
TEST(n5);
int n6[] = {0,1,2,9,7,5,4,2,1};
TEST(n6);
int n7[] = {1,2,1,2,1};
TEST(n7);
int n8[] = {1,2,1,2,3,1};
TEST(n8);
int n9[] = {1,2,3,2,4,2,1};
TEST(n9);
int n10[] = {1,3,1,2,1,3,1};
TEST(n10);
return 0;
}