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 的大作中提到】
: 二分查找呗 找中间俩数 比较看是升序还是降序 升序在后一半找 降序在前一半找
|
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 的大作中提到】
: 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 的大作中提到】
: 这么快就加到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 的大作中提到】
: 它给的测试例子里，其它的数不是排好序的。难点就是在这。比如这个例子
: [100,102,104,7,9,11,4,3]
|
l*********u
发帖数: 19053 | 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******g
发帖数: 3616 | 11 不二分就是O(n)吧。。。。
【在 l*********u 的大作中提到】
: 好象没必要２分。从前后第２个开始，同时前后对扫，找下降的点，先找到的就是一个
: peak。
|
l*********u
发帖数: 19053 | 12 噢。。。不会算时间复杂度 ：）前后同时找，找到就停，也算O(n)？
【在 b******g 的大作中提到】
: 不二分就是O(n)吧。。。。
|
p**t
发帖数: 157 | 13 你这开销显然O(n)啊。。。
【在 l*********u 的大作中提到】
: 好象没必要２分。从前后第２个开始，同时前后对扫，找下降的点，先找到的就是一个
: 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 的大作中提到】
: 噢。。。不会算时间复杂度 ：）前后同时找，找到就停，也算O(n)？
|
l*********u
发帖数: 19053 | 15 谢谢讲解。
【在 p**t 的大作中提到】
: 平均你需要遍历的数组元素个数是O(n)的 显然复杂度是O(n)
: 具体点说 最简单的例子 就一个peak 在数组的第k个位置
: 假设k是从1-n的uniform distribution
: 于是你需要查找的次数是min(k,n-k) 也就是一个(1 ~ n/2)的U分布
: 其平均值显然是O(n)的
|
