l***i
发帖数: 1309 | 1 Given an array of distinct integers, a[0] to a[n-1]
a[i] is local maxima if a[i] > a[i-1] and a[i] > a[i+1] provided the
neighbor exists.
Find any local maxima in sublinear time. |
e****e
发帖数: 418 | 2 Any hidden trick?
Here is my Java code.
Integer[] findLocalMaxima(int[] a) {
if ( a == null || a.length == 0 )
throw new RuntimeException();
List list = new ArrayList();
for ( int i = 1; i < a.length - 1; i++ ) {
if ( a[i] > a[i-1] && a[i] > a[i+1] )
list.add( a[i] );
}
return (Integer[])list.toArray(new Integer[]{});
} |
z********i
发帖数: 568 | 3 可能吗？假设a[0]..a[i]是递增，a[i+1]..a[-1]是递增。
如果a[i+1]
But i could be anywhere in 0..n-1.
【在 l***i 的大作中提到】
: Given an array of distinct integers, a[0] to a[n-1]
: a[i] is local maxima if a[i] > a[i-1] and a[i] > a[i+1] provided the
: neighbor exists.
: Find any local maxima in sublinear time.
|
l***i
发帖数: 1309 | 4 The solution will find a[i] in log(n) time in your case, and in general.
【在 z********i 的大作中提到】
: 可能吗？假设a[0]..a[i]是递增，a[i+1]..a[-1]是递增。
: 如果a[i+1]: But i could be anywhere in 0..n-1.
|
z********i
发帖数: 568 | 5 洗耳恭听。
【在 l***i 的大作中提到】
: The solution will find a[i] in log(n) time in your case, and in general.
|
l***i
发帖数: 1309 | 6 I learned from someone else.
The idea is binary search.
Take a[n/2], then check its left and right, if a[n/2] is max among the three
, then we get a[n/2] as local maxima.
Otherwise w.l.o.g we can assume a[n/2 - 1] < a[n/2] < a[n/2 + 1]
Now there has to be a local maxima in a[n/2+1] to a[n-1]. So you recurse on
the right half of the array. |
p*****2
发帖数: 21240 | 7 能不能给几个例子？
这题可能没有maxima, 也可能有多个maxima吗？ |
C***U
发帖数: 2406 | 8 这谁教你的?
three
on
【在 l***i 的大作中提到】
: I learned from someone else.
: The idea is binary search.
: Take a[n/2], then check its left and right, if a[n/2] is max among the three
: , then we get a[n/2] as local maxima.
: Otherwise w.l.o.g we can assume a[n/2 - 1] < a[n/2] < a[n/2 + 1]
: Now there has to be a local maxima in a[n/2+1] to a[n-1]. So you recurse on
: the right half of the array.
|
c********t
发帖数: 5706 | 9 请问什么是sublinear time？和linear time有什么区别？wiki上的解释没看懂。
【在 l***i 的大作中提到】
: Given an array of distinct integers, a[0] to a[n-1]
: a[i] is local maxima if a[i] > a[i-1] and a[i] > a[i+1] provided the
: neighbor exists.
: Find any local maxima in sublinear time.
|
l*****i
发帖数: 136 | 10 O(n^p), 0
【在 c********t 的大作中提到】
: 请问什么是sublinear time？和linear time有什么区别？wiki上的解释没看懂。
|
|
|
z********i
发帖数: 568 | 11 In the example: a[0]..a[i] increasing order, a[i+1]..a[n-1] increasing order.
1) i>n/2, the assumption to further search the right half is correct.
2) i
three
on
【在 l***i 的大作中提到】
: I learned from someone else.
: The idea is binary search.
: Take a[n/2], then check its left and right, if a[n/2] is max among the three
: , then we get a[n/2] as local maxima.
: Otherwise w.l.o.g we can assume a[n/2 - 1] < a[n/2] < a[n/2 + 1]
: Now there has to be a local maxima in a[n/2+1] to a[n-1]. So you recurse on
: the right half of the array.
|
l***i
发帖数: 1309 | 12 if a[i+1]..a[n-1] is in increasing order, then a[n-1] is a local maxima. So
search right half is correct regardless of i > n/2 or i < n/2.
this is a homework problem from MIT algorithm class.
order.
【在 z********i 的大作中提到】
: In the example: a[0]..a[i] increasing order, a[i+1]..a[n-1] increasing order.
: 1) i>n/2, the assumption to further search the right half is correct.
: 2) i:
: three
: on
|
z********i
发帖数: 568 | 13 If a[n-1] is a maximal when a[n-1]>a[n-2], it is correct.
So
【在 l***i 的大作中提到】
: if a[i+1]..a[n-1] is in increasing order, then a[n-1] is a local maxima. So
: search right half is correct regardless of i > n/2 or i < n/2.
: this is a homework problem from MIT algorithm class.
:
: order.
|
l***i
发帖数: 1309 | 14 Yes, the problem says a[i] has to be bigger than its left and right neighbor
, provided such neighbor exists. |
d***n
发帖数: 65 | 15 如果这样定义local maxima那么binary search自然可以
So
【在 l***i 的大作中提到】
: if a[i+1]..a[n-1] is in increasing order, then a[n-1] is a local maxima. So
: search right half is correct regardless of i > n/2 or i < n/2.
: this is a homework problem from MIT algorithm class.
:
: order.
|
