2D Peak Finding - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

题目

峰值元素是指其值⼤于上下左右相邻值的元素。给定⼀个二维数组arr，找到峰值并返回其索引。二维数组可能包含多个峰值，返回任何⼀个峰值所在位置即可。

图解

详解

二维峰值查找

分治思想

定义：将一个难以解决的大问题分割成些规模小的相同问题，以便各击破，分而治之

1. 分解：将原问题分解为若干个规模较小。相互独立，与原问题形式相同的子问题
2. 解决：若子问题规模小而容易被解决则直接解否则递归地解各子问题
3. 合并：将各个子问题的解台并为原问题的解

算法思路

算法1：顺序搜索 (Brute Force)

• 思路：从左上⻆[0][0]到右下⻆[n][m]遍历每个元素，依次与上下左右的元素⽐较
• T(m, n) = O(mn)

算法2：全局最大值Global Max和局部最大值Local Max

• 思路：
  1. 找到每一列的最大值C1, C2, Cm O(mn)
  2. 所有每一列的最大值按顺序排成一列Lm
  3. 找到Lm中的局部峰值O(logm)
  • T(m, n) = O(mn) + O(logm)

算法3：全局最大值Global Max和局部最大值Local Max（二分搜索）

• 思路：与算法1类似，但不需要先找到每一列的最大值，根据给定的二维数组可得知Lm肯定有m个元素，因此可以先对空数组Lm使用寻找峰值法，根据mid指针的位置找到Lm中对应的空元素所代表的列的最大值，比较相邻值判断爬升方向

  1. 找到Lm中的局部峰值
  2. 根据mid指针的位置，找到Lm中对应的空元素所代表的列的最大值 0(n)
  3. 只比较相邻值判断爬升方向
  4. 最后的一列肯定是纵向最大值，横向峰值

• 时间复杂度分析

算法4：分治思想

• 思路：

  1. 对二维数组做如上图的划分，形成四个子区域
  2. 找到“田”字上的最大元素a
  3. 若a是峰值，则返回a；否则进入比a大（或等于）的元素所在的区域，递归求解
     • 图中“田”字上最大元素为20，上方22比它大，进入上方的子区域继续求解

• 时间复杂度分析