I
一个元素互不相同的一维数组，要求$O(\log n)$找到一个峰值，即大于左右两边值的位置。a[-1]和a[n]可认为是$-\infty$。
考虑二分答案mid，如果a[mid] > a[mid + 1]，在[l, mid - 1]间肯定存在答案，因为可以把mid + 1视作n这个角色；同理a[mid] < a[mid + 1]，在[mid + 1, r - 1]间肯定有答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| impl Solution {
pub fn find_peak_element(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut l = 0;
let mut r = n - 1;
let mut ans = 0;
while l <= r {
let mid = (l + r) >> 1;
let left = if mid == 0 {
true
} else {
nums[mid] > nums[mid - 1]
};
let right = if mid == n - 1 {
true
} else {
nums[mid] > nums[mid + 1]
};
if left && right {
ans = mid;
break;
} else if left {
l = mid + 1;
} else if right {
r = mid - 1;
} else {
l = mid + 1;
}
}
ans as i32
}
}
|
II
二维版本，要求$O(n \log m)$。没做出来0.0，好菜
考虑二分行mid，再考虑这一行中的最大值a[mid][j]，如果a[mid][j] < a[mid + 1][j]，则行[mid + 1, r - 1]肯定有答案，因为a[mid + 1][j]大于mid行的所有元素，而由于不断往比自己大的邻居移动一定能找到解，按这种方案一定不会穿越mid行；同理a[mid][j] < a[mid - 1][j]，则行[l, mid - 1]肯定有答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| impl Solution {
pub fn find_peak_grid(mat: Vec<Vec<i32>>) -> Vec<i32> {
let mut l = 0;
let mut r = mat.len() - 1;
while l <= r {
let mid = (l + r) >> 1;
let index = mat[mid].iter().enumerate()
.max_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal))
.map(|(index, _)| index).unwrap();
if mid >= 1 && mat[mid][index] < mat[mid - 1][index] {
r = mid - 1;
continue;
}
if mid + 1 < mat.len() && mat[mid][index] < mat[mid + 1][index] {
l = mid + 1;
continue;
}
return vec![mid as i32, index as i32];
}
vec![]
}
}
|