求问一题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求问一题

求问一题# JobHunting - 待字闺中

l*12014-12-04 08:12

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*t2014-12-04 08:12

2 楼

二分查找呗找中间俩数比较看是升序还是降序升序在后一半找降序在前一半找

l*12014-12-04 08:12

3 楼

它给的测试例子里，其它的数不是排好序的。难点就是在这。比如这个例子
[100,102,104,7,9,11,4,3]

【在 p**t 的大作中提到】

: 二分查找呗找中间俩数比较看是升序还是降序升序在后一半找降序在前一半找

f*b2014-12-04 08:12

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*12014-12-04 08:12

5 楼

靠谱，赞思路！

【在 f***b 的大作中提到】

: 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*t2014-12-04 08:12

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*b2014-12-04 08:12

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*a2014-12-04 08:12

8 楼

请问 auto peek = [&](int id) 这种用法是什么意思？
后面为什么可以peek(m) 这么用？

【在 f***b 的大作中提到】

: 这么快就加到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*t2014-12-04 08:12

9 楼

不需要排好序比如你这个例子里第一次找到7，9 于是在后一半继续找到11，4 前一
半 9，11 后一半这时候就剩9，11，4 满足条件返回11 结束
题目也说了多个拐点挑一个返回就行

它给的测试例子里，其它的数不是排好序的。难点就是在这。比如这个例子[100,102,
104,7,9,11,4,3]

【在 l**********1 的大作中提到】

: 它给的测试例子里，其它的数不是排好序的。难点就是在这。比如这个例子
: [100,102,104,7,9,11,4,3]

l*u2014-12-04 08:12

10 楼

好象没必要２分。从前后第２个开始，同时前后对扫，找下降的点，先找到的就是一个
peak。

【在 l**********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]

b*g2014-12-04 08:12

11 楼

不二分就是O(n)吧。。。。

【在 l*********u 的大作中提到】

: 好象没必要２分。从前后第２个开始，同时前后对扫，找下降的点，先找到的就是一个
: peak。

l*u2014-12-04 08:12

12 楼

噢。。。不会算时间复杂度　：）前后同时找，找到就停，也算O(n)？

【在 b******g 的大作中提到】

: 不二分就是O(n)吧。。。。

p*t2014-12-04 08:12

13 楼

你这开销显然O(n)啊。。。

【在 l*********u 的大作中提到】

: 好象没必要２分。从前后第２个开始，同时前后对扫，找下降的点，先找到的就是一个
: peak。

p*t2014-12-04 08:12

14 楼

平均你需要遍历的数组元素个数是O(n)的显然复杂度是O(n)
具体点说最简单的例子就一个peak 在数组的第k个位置
假设k是从1-n的uniform distribution
于是你需要查找的次数是min(k,n-k) 也就是一个(1 ~ n/2)的U分布
其平均值显然是O(n)的

【在 l*********u 的大作中提到】

: 噢。。。不会算时间复杂度　：）前后同时找，找到就停，也算O(n)？

l*u2014-12-04 08:12

15 楼

谢谢讲解。

【在 p**t 的大作中提到】

: 平均你需要遍历的数组元素个数是O(n)的显然复杂度是O(n)
: 具体点说最简单的例子就一个peak 在数组的第k个位置
: 假设k是从1-n的uniform distribution
: 于是你需要查找的次数是min(k,n-k) 也就是一个(1 ~ n/2)的U分布
: 其平均值显然是O(n)的