Find Peak Element II
2024-10-06 06:58:41
Description
Given an integer matrix A which has the following features :
- The numbers in adjacent positions are different.
- The matrix has
nrows andmcolumns. - For all
i < n,A[i][0] < A[i][1] && A[i][m - 2] > A[i][m - 1]. - For all
j < m,A[0][j] < A[1][j] && A[n - 2][j] > A[n - 1][j]
We define a position [i, j] is a peak if:
A[i][j] > A[i + 1][j] && A[i][j] > A[i - 1][j] &&
A[i][j] > A[i][j + 1] && A[i][j] > A[i][j - 1]
Find a peak element in this matrix. Return the index of the peak.
Guarantee that there is at least one peak, and if there are multiple peaks, return any one of them.
Example
Example 1:
Input:
[
[1, 2, 3, 6, 5],
[16,41,23,22, 6],
[15,17,24,21, 7],
[14,18,19,20,10],
[13,14,11,10, 9]
]
Output: [1,1]
Explanation: [2,2] is also acceptable. The element at [1,1] is 41, greater than every element adjacent to it.
Example 2:
Input:
[
[1, 5, 3],
[4,10, 9],
[2, 8, 7]
]
Output: [1,1]
Explanation: There is only one peek.
Challenge
Solve it in O(n+m) time.
If you come up with an algorithm that you thought it is O(nlogm) or O(mlogn), can you prove it is actually O(n+m) or propose a similar but O(n+m) algorithm?
思路：http://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf 或者使用二分(时间复杂度为O(nlog(n)).
// O(n + m) 解法
class Solution {
/**
* @param A: An integer matrix
* @return: The index of the peak
*/
public List<Integer> find(int x1, int x2, int y1, int y2, int[][] A) { int mid1 = x1 + (x2 - x1) / 2;
int mid2 = y1 + (y2 - y1) / 2; int x = mid1, y = mid2;
int max = A[mid1][mid2];
for (int i = y1; i <= y2; ++i)
if (A[mid1][i] > max) {
max = A[mid1][i];
x = mid1;
y = i;
} for (int i = x1; i <= x2; ++i)
if (A[i][mid2] > max) {
max = A[i][mid2];
x = i;
y = mid2;
} boolean isPeak = true;
if (A[x - 1][y] > A[x][y]) {
isPeak = false;
x -= 1;
} else if (A[x + 1][y] > A[x][y]) {
isPeak = false;
x += 1;
} else if (A[x][y - 1] > A[x][y]) {
isPeak = false;
y -= 1;
} else if (A[x][y + 1] > A[x][y]) {
isPeak = false;
y += 1;
} if (isPeak) {
return new ArrayList<Integer>(Arrays.asList(x, y));
} if (x >= x1 && x < mid1 && y >= y1 && y < mid2) {
return find(x1, mid1 - 1, y1, mid2 - 1, A);
} if (x >= 1 && x < mid1 && y > mid2 && y <= y2) {
return find(x1, mid1 - 1, mid2 + 1, y2, A);
} if (x > mid1 && x <= x2 && y >= y1 && y < mid2) {
return find(mid1 + 1, x2, y1, mid2 - 1, A);
} if (x >= mid1 && x <= x2 && y > mid2 && y <= y2) {
return find(mid1 + 1, x2, mid2 + 1, y2, A);
} return new ArrayList<Integer>(Arrays.asList(-1, -1)); } public List<Integer> findPeakII(int[][] A) {
// write your code here
int n = A.length;
int m = A[0].length;
return find(1, n - 2, 1, m - 2, A);
}
} class Solution {
/**
* @param A: An integer matrix
* @return: The index of the peak
*/
public List<Integer> findPeakII(int[][] A) {
// this is the nlog(n) method
int low = 1, high = A.length - 2;
List<Integer> ans = new ArrayList<Integer>();
while (low <= high) {
int mid = (low + high) / 2;
int col = find(mid, A);
if (A[mid][col] < A[mid - 1][col]) {
high = mid - 1;
} else if (A[mid][col] < A[mid + 1][col]) {
low = mid + 1;
} else {
ans.add(mid);
ans.add(col);
break;
}
}
return ans;
} int find(int row, int[][] A) {
int col = 0;
for (int i = 0; i < A[row].length; i++) {
if (A[row][i] > A[row][col]) {
col = i;
}
}
return col;
}
}
最新文章
- JMeter学习-024-JMeter 命令行（非GUI）模式详解（二）-执行代理设置
- Clr静态数据Table-Valued函数
- 深入理解KMP算法之续篇
- 【BZOJ2223/3524】[Coci 2009]PATULJCI
- 在Hadoop-2.2.0集群上安装 Hive-0.13.1 with MySQL
- 安卓开发_浅谈Android动画（一）
- unity, 用unity profiler进行真机profile，需要退出360
- org.springframework.core.NestedIOException
- BZOJ 2456
- ubuntu环境配置
- C#核编之X++详解
- Qt在windows与Mac OS中获取执行程序版本号
- 学习英语每日一 On the house. 赠品
- GCD应用场景
- 【响应式编程的思维艺术】 （5）Angular中Rxjs的应用示例
- Docker 搭建pxc集群 + haproxy + keepalived 高可用（一）
- BBS论坛（二十八）
- 【汇总目录】Java
- map映射巧用 A-B Problems
- makefile中一些编译器选项