h**i
发帖数: 12 | 1 一个数组，保证前半部递增，后半部递减，求数组最大值。二分查找，没写出来。大家
有近期面的，练一下。 |
v****a
发帖数: 236 | 2 谢谢楼主！bless！数组元素有重复吗？
【在 h**i 的大作中提到】
: 一个数组，保证前半部递增，后半部递减，求数组最大值。二分查找，没写出来。大家
: 有近期面的，练一下。
|
a***y
发帖数: 852 | 3 最大值不是中间那个值？
还是我理解错了
【在 h**i 的大作中提到】
: 一个数组，保证前半部递增，后半部递减，求数组最大值。二分查找，没写出来。大家
: 有近期面的，练一下。
|
l******a
发帖数: 14 | 4 二分，如果中值比左右邻居都大，return中值，否则哪边邻居大在哪边找 |
l*********8
发帖数: 4642 | 5 有意思，没见过
My 2 cents:
第一个元素记为s
最后一个元素记为e
中间取两点a, b
如果s, a, b不单调递增， 则递归搜索[s,b]
otherwise, 递归搜索[a, e]
【在 h**i 的大作中提到】
: 一个数组，保证前半部递增，后半部递减，求数组最大值。二分查找，没写出来。大家
: 有近期面的，练一下。
|
r****r
发帖数: 159 | |
f*****u
发帖数: 308 | 7 public int findMax(int[] A, int start, int end) {
// return conditions
if(end == start) return A[start];
if(end - start == 1) return Math.max(A[start], A[end]);
int mid = start + (end-start)/2;
if(A[mid] > A[mid-1] && A[mid] > A[mid+1]) return A[mid];
if(A[mid-1] > A[mid]) return findMax(A, start, mid);
else return findMax(A, mid, end);
} |
m******s
发帖数: 1469 | 8 Zan!
【在 h**i 的大作中提到】
: 一个数组，保证前半部递增，后半部递减，求数组最大值。二分查找，没写出来。大家
: 有近期面的，练一下。
|
w******n
发帖数: 61 | 9 跟leetcode那个rotated array是不是差不多？有重复值的时候要多分几种情况？ |
l*********8
发帖数: 4642 | 10 恩，就是这样。
我发现我以前可能见过这题，又忘了。。。
【在 f*****u 的大作中提到】
: public int findMax(int[] A, int start, int end) {
: // return conditions
: if(end == start) return A[start];
: if(end - start == 1) return Math.max(A[start], A[end]);
:
: int mid = start + (end-start)/2;
: if(A[mid] > A[mid-1] && A[mid] > A[mid+1]) return A[mid];
: if(A[mid-1] > A[mid]) return findMax(A, start, mid);
: else return findMax(A, mid, end);
: }
|
i*********n
发帖数: 58 | 11 int findMaxRecur(vector& num, int begin, int end)
{
if (begin == end)
return num[begin];
if (begin + 1 == end)
return std::max(num[begin], num[end]);
int mid = (begin + end) / 2;
if (num[begin] < num[mid] && num[mid] < num[end]) {
return num[end];
}
else {
return std::max(
findMaxRecur(num, begin, mid),
findMaxRecur(num, mid + 1, end));
}
} |
z***e
发帖数: 58 | 12 其实可以更简单的， 直接用 A[mid] 和 A[mid-1] 和 A[mid+1] 比较判断单调性，如
果是A[mid-1] A[mid+1] 就是结果， A[mid-1] < A[mid]< A[mid+1] mid在
递增区间上，更新 left = mid, 反之则在递减区间上 right =mid . 其余的照抄二分
的iterative逻辑就好了，也不用递归。 |
r****7
发帖数: 2282 | 13 你这个O(n)的复杂度了
【在 i*********n 的大作中提到】
: int findMaxRecur(vector& num, int begin, int end)
: {
: if (begin == end)
: return num[begin];
: if (begin + 1 == end)
: return std::max(num[begin], num[end]);
: int mid = (begin + end) / 2;
: if (num[begin] < num[mid] && num[mid] < num[end]) {
: return num[end];
: }
|
