l**********1 发帖数: 415 | 1 lintcode 上的一个题, 要求时间复杂度是 O(lgn)
There is an integer array which has the following features:
* The numbers in adjacent positions are different.
* A[0] < A[1] && A[A.length - 2] > A[A.length - 1].
We define a position P is a peek if A[P] > A[P-1] && A[P] > A[P+1].
Find a peak in this array. Return the index of the peak.
Note
The array may contains multiple peeks, find any of them.
Example
[1, 2, 1, 3, 4, 5, 7, 6]
return index 1 (which is number 2) or 6 (which is number 7) |
p**t 发帖数: 157 | 2 二分查找呗 找中间俩数 比较看是升序还是降序 升序在后一半找 降序在前一半找 |
l**********1 发帖数: 415 | 3 它给的测试例子里,其它的数不是排好序的。难点就是在这。比如这个例子
[100,102,104,7,9,11,4,3]
【在 p**t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 二分查找呗 找中间俩数 比较看是升序还是降序 升序在后一半找 降序在前一半找
|
f***b 发帖数: 21 | 4 int find(int A[], int n) {
int l = 1, r = n-2;
while (l <= r) {
int m = l + (r-l)/2;
if(A[m] > A[m-1] && A[m] > A[m+1])
return m;
else {
if(A[m] < A[m+1]) {
l = m+1;
} else {
r = m-1;
}
}
}
return -1;
}
这么写靠谱不 |
l**********1 发帖数: 415 | 5 靠谱,赞思路!
【在 f***b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : int find(int A[], int n) { : int l = 1, r = n-2; : while (l <= r) { : int m = l + (r-l)/2; : if(A[m] > A[m-1] && A[m] > A[m+1]) : return m; : else { : if(A[m] < A[m+1]) { : l = m+1; : } else {
|
f**********t 发帖数: 1001 | 6 int OnePeek(int arr[], int n) {
if (n < 3) {
return -1;
}
int l = 1;
int r = n - 2;
while (l <= r) {
if (l == r) {
return l;
}
if (l + 1 == r) {
return arr[l] < arr[r] ? l : r;
}
int m = (l + r) / 2;
if (arr[m] < arr[m + 1]) {
l = m + 1;
} else if (arr[m - 1] > arr[m]) {
r = m - 1;
} else {
return m;
}
}
} |
f***b 发帖数: 21 | 7 这么快就加到leetcode了。
改了下代码,可以ac:
class Solution {
public:
int findPeakElement(const vector &A) {
auto peek = [&](int id){
if (id < 0 || id >= A.size()) return INT_MIN;
else return A[id];
};
int l = 0, r = A.size()-1;
while (l <= r) {
int m = l + (r-l)/2;
if(peek(m) > peek(m-1) && peek(m) > peek(m+1))
return m;
else {
if(peek(m) < peek(m+1)) {
l = m+1;
} else {
r = m-1;
}
}
}
return 0;
}
}; |
m******a 发帖数: 84 | 8 请问 auto peek = [&](int id) 这种用法是什么意思?
后面为什么可以peek(m) 这么用?
【在 f***b 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这么快就加到leetcode了。 : 改了下代码,可以ac: : class Solution { : public: : int findPeakElement(const vector &A) { : auto peek = [&](int id){ : if (id < 0 || id >= A.size()) return INT_MIN; : else return A[id]; : }; :
|
p**t 发帖数: 157 | 9 不需要排好序 比如你这个例子里 第一次找到7,9 于是在后一半继续 找到11,4 前一
半 9,11 后一半 这时候就剩9,11,4 满足条件 返回11 结束
题目也说了多个拐点挑一个返回就行
它给的测试例子里,其它的数不是排好序的。难点就是在这。比如这个例子[100,102,
104,7,9,11,4,3]
【在 l**********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 它给的测试例子里,其它的数不是排好序的。难点就是在这。比如这个例子 : [100,102,104,7,9,11,4,3]
|
l*********u 发帖数: 19053 | 10 好象没必要2分。从前后第2个开始,同时前后对扫,找下降的点,先找到的就是一个
peak。
【在 l**********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : lintcode 上的一个题, 要求时间复杂度是 O(lgn) : There is an integer array which has the following features: : * The numbers in adjacent positions are different. : * A[0] < A[1] && A[A.length - 2] > A[A.length - 1]. : We define a position P is a peek if A[P] > A[P-1] && A[P] > A[P+1]. : Find a peak in this array. Return the index of the peak. : Note : The array may contains multiple peeks, find any of them. : Example : [1, 2, 1, 3, 4, 5, 7, 6]
|
|
|
b******g 发帖数: 3616 | 11 不二分就是O(n)吧。。。。
【在 l*********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好象没必要2分。从前后第2个开始,同时前后对扫,找下降的点,先找到的就是一个 : peak。
|
l*********u 发帖数: 19053 | 12 噢。。。不会算时间复杂度 :)前后同时找,找到就停,也算O(n)?
【在 b******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不二分就是O(n)吧。。。。
|
p**t 发帖数: 157 | 13 你这开销显然O(n)啊。。。
【在 l*********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好象没必要2分。从前后第2个开始,同时前后对扫,找下降的点,先找到的就是一个 : peak。
|
p**t 发帖数: 157 | 14 平均你需要遍历的数组元素个数是O(n)的 显然复杂度是O(n)
具体点说 最简单的例子 就一个peak 在数组的第k个位置
假设k是从1-n的uniform distribution
于是你需要查找的次数是min(k,n-k) 也就是一个(1 ~ n/2)的U分布
其平均值显然是O(n)的
【在 l*********u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 噢。。。不会算时间复杂度 :)前后同时找,找到就停,也算O(n)?
|
l*********u 发帖数: 19053 | 15 谢谢讲解。
【在 p**t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 平均你需要遍历的数组元素个数是O(n)的 显然复杂度是O(n) : 具体点说 最简单的例子 就一个peak 在数组的第k个位置 : 假设k是从1-n的uniform distribution : 于是你需要查找的次数是min(k,n-k) 也就是一个(1 ~ n/2)的U分布 : 其平均值显然是O(n)的
|