试题详情
简答题若在矩阵A中存在一个元素ai，j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有马鞍点的算法，并分析最坏情况下的时间复杂度。
  • 在矩阵中逐行寻找该行中的最小值，然后对其所在的列寻找最大值，如果该列上的最大值与该行上的最小值相等，则说明该元素是鞍点，将它所在行号和列号输出。
    具体算法如下：

    分析算法，外层for循环共执行n次，内层第一个for循环执行m次，第二个for循环最坏情况下执行n
    次，所以，最坏情况下的时间复杂度为Ｏ（mn+n2）。分析算法，外层for循环共执行n次，内层第一个for循环执行m次，第二个for循环最坏情况下执行n
    次，所以，最坏情况下的时间复杂度为Ｏ（mn+n2）。

  • 关注下方微信公众号，在线模考后查看

热门试题