算法练习(72): 矩阵的局部最小元素(1.4.19)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 矩阵的概念
• 线性代数概念
• 凯利介绍

题目

1.4.19 矩阵的局部最小元素。给定一个含有 N^2 个不同整数的 N×N 数组 a[]。设计一个运算时间和 N 成正比的算法来找出一个局部最小元素：满足 a[i][j] < a[i+1][j]、a[i][j] < a[i][j+1]、a[i][j] < a[i-1][j] 以及 a[i][j] < a[i][j-1] 的索引 i 和 j。程序运行时间在最坏情况下应该和 N 成正比。

---

1.4.19 Local minimum of a matrix. Given an N-by-N array a[] of N 2 distinct integers, design an algorithm that runs in time proportional to N to find a local minimum: a pair of indices i and j such that a[i][j] < a[i+1][j], a[i][j] < a[i][j+1], a[i][j] < a[i-1][j], and a[i][j] < a[i][j-1]. The running time of your program should be proportional to N in the worst case.

分析

我们首先要注意的是，这是一个正方形的矩阵。关于矩阵的定义这里不多说了，这是个很宏大的主题，这里就贴点概念性的东西吧。

在数学中，矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合，最早来自于方程组的系数及常数所构成的方阵。这一概念由19世纪英国数学家凯利(又译做“凯莱”)首先提出。

所以，矩阵的发明者是凯利，那下面讲一下关于凯利这个人。

凯利是英国数学家。生于里士满 (Richmond)，卒于剑桥。17岁时考入剑桥大学的三一学院 ，毕业后留校讲授数学，几年内发表论文数十篇。1846年转攻法律学，三年后成为律师，工作卓有成效。任职期间，他仍业馀研究数学，并结识数学家西尔维斯特（Sylvester）。1863年应邀返回剑桥大学任数学教授。他得到牛津大学、都柏林大学和莱顿大学的名誉学位。1859年当选为伦敦皇家学会会员。

凯利一生仅出版一本专著，便是1876年的《椭圆函数初论》，但发表了近1000篇论文，其中一些影响极为深远。凯利在劝说剑桥大学接受女学生中起了很大作用。他在生前得到了他所处时代一位科学家可能得到的几乎所有重要荣誉。 Arthur Cayley

这道题有一定难度，在Stack Overflow上也有一些回答，但给出代码的寥寥无几，我们先列几个Stack Overflow上的提问以及回答吧：

Find local minimum in n x n matrix in O(n) time

上面给的答案就是一种“滚下山”（roll downhill）的方式，首先找到中间行，并在中间行中找到该行的最小值，然后判断它在该列中是不是局部最小值，如果是的话，那就返回这个值，否则向该列的小一侧方向移动，如此循环往复。

Peak Finding

麻省理工学院的算法入门课也有这道题的详细的介绍 1

题目的介绍：假设你掉入了一个群山连绵的地方，很口渴，需要找个水池，那方法是怎么样的。（看来算法真的还是有用处的，可以自救）

2
提出问题：找出局部最大值或者最小值
3

建模：把这个问题归结为二维数组（或矩阵）的找局部最大值问题

4

看这个数组的中间元素不能拆分这个问题

5

找出这个矩阵每列的最大值，列出来

6

如果中间列的最大值不是局部最大值，那么找到它的更大值的邻居。以此类推。这也正是前面我们提到的滚下山”（roll downhill）的方式。

7

算出时间复杂度是nlgn，能否更快？

8
方法：将矩阵分为四个象限，得到四个小矩阵
9
分析：随便找个小矩阵中取得局部最大值，那在整个大矩阵中也是局部最大值，这样就相当于只需要解决大问题中的一个小问题。
10

算出复杂度是n，完美解决！

如上面的图可知，他们解决的是局部最大值的问题，但其实我们的局部最小值也是一样的解决方案。
我们的先把滚下山的解法写出来，因为这种比较好理解

public class MatrixLocalMinimum {
    private static class IndexPath {
        int row;
        int column;
    }
    
    private IndexPath miniMumIndexPathOfItem(int[][] matrix,IndexPath indexPath){
        IndexPath resultItem = new IndexPath();
        resultItem.column = indexPath.column;
        resultItem.row = indexPath.row;

        int currentItem = matrix[indexPath.row][indexPath.column];
        int left  = matrix[indexPath.row][(indexPath.column - 1) >= 0 ? (indexPath.column - 1) : indexPath.column  ];
        int right = matrix[indexPath.row][(indexPath.column + 1) <= matrix.length ? (indexPath.column + 1) : indexPath.column  ];
        int top    = matrix[(indexPath.row - 1 ) >= 0 ? (indexPath.row - 1 ) : indexPath.row][indexPath.column];
        int bottom = matrix[(indexPath.row + 1 ) <= matrix.length ? (indexPath.row + 1 ) : indexPath.row][indexPath.column];

        int[] rounder = {left,right,top,bottom,currentItem};
        Arrays.sort(rounder);
        if (rounder[0] == currentItem){
            System.out.print("row:"+resultItem.row + "column:" + resultItem.column);
            return resultItem;
        }else if (rounder[0] == left){
            resultItem.column = (indexPath.column - 1);
            miniMumIndexPathOfItem(matrix,resultItem);
        }else if (rounder[0] == right){
            resultItem.column = (indexPath.column + 1);
            miniMumIndexPathOfItem(matrix,resultItem);
        }else if (rounder[0] == top) {
            resultItem.row = (indexPath.row - 1);
            miniMumIndexPathOfItem(matrix,resultItem);
        }else if (rounder[0] == bottom) {
            resultItem.row = (indexPath.row + 1);
            miniMumIndexPathOfItem(matrix,resultItem);
        }else{

        }
        return resultItem;
    }

    /**
     * 找出数组中的最小值的index
     */
    private static int miniumOfArray(int[] x) {
        int indexOfMinium = 0;
        int itemOfMinium = Integer.MAX_VALUE;
        for (int i = 0; i < x.length; i++) {
            if (x[i] < itemOfMinium) {
                itemOfMinium = x[i];
                indexOfMinium = i;
            }
        }
        return indexOfMinium;
    }

    public static void main(String[] args) {
        int[][] matrix = { 
                { 11,  2,  3,  4, 102 }, 
                { 53,  6,  7, 18, 101 },
                { 12, 11, 10, 89, 100 }, 
                { 14,  1,  8,  5,   0 },
                { 114,51, 58, 55,  99 }
                };
        int middleRow = matrix.length / 2;
        int[] row = matrix[middleRow];
        int index = miniumOfArray(row);
        MatrixLocalMinimum localMinimum = new MatrixLocalMinimum();
        IndexPath indexPath = new IndexPath();
        indexPath.row = middleRow;
        indexPath.column = index;
        IndexPath resultIndexPath = localMinimum.miniMumIndexPathOfItem(matrix,indexPath);
    }

}

MatrixLocalMinimum.java

但答案要求的是复杂度为n的解法，我们通过获取submatrix的解法实现：

答案

代码索引

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。