本系列博客習(xí)題來(lái)自《算法(第四版)》，算是本人的讀書(shū)筆記，如果有人在讀這本書(shū)的，歡迎大家多多交流。為了方便討論，本人新建了一個(gè)微信群(算法交流)，想要加入的，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝。另外，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論

算法(第4版)

知識(shí)點(diǎn)

• 矩陣的概念
• 線性代數(shù)概念
• 凱利介紹

題目

1.4.19 矩陣的局部最小元素。給定一個(gè)含有 N^2 個(gè)不同整數(shù)的 N×N 數(shù)組 a[]。設(shè)計(jì)一個(gè)運(yùn)算時(shí)間和 N 成正比的算法來(lái)找出一個(gè)局部最小元素：滿足 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。程序運(yùn)行時(shí)間在最壞情況下應(yīng)該和 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.

分析

我們首先要注意的是，這是一個(gè)正方形的矩陣。關(guān)于矩陣的定義這里不多說(shuō)了，這是個(gè)很宏大的主題，這里就貼點(diǎn)概念性的東西吧。

在數(shù)學(xué)中，矩陣（Matrix）是一個(gè)按照長(zhǎng)方陣列排列的復(fù)數(shù)或?qū)崝?shù)集合，最早來(lái)自于方程組的系數(shù)及常數(shù)所構(gòu)成的方陣。這一概念由19世紀(jì)英國(guó)數(shù)學(xué)家凱利(又譯做“凱萊”)首先提出。

所以，矩陣的發(fā)明者是凱利，那下面講一下關(guān)于凱利這個(gè)人。

凱利是英國(guó)數(shù)學(xué)家。生于里士滿 (Richmond)，卒于劍橋。17歲時(shí)考入劍橋大學(xué)的三一學(xué)院 ，畢業(yè)后留校講授數(shù)學(xué)，幾年內(nèi)發(fā)表論文數(shù)十篇。1846年轉(zhuǎn)攻法律學(xué)，三年后成為律師，工作卓有成效。任職期間，他仍業(yè)馀研究數(shù)學(xué)，并結(jié)識(shí)數(shù)學(xué)家西爾維斯特（Sylvester）。1863年應(yīng)邀返回劍橋大學(xué)任數(shù)學(xué)教授。他得到牛津大學(xué)、都柏林大學(xué)和萊頓大學(xué)的名譽(yù)學(xué)位。1859年當(dāng)選為倫敦皇家學(xué)會(huì)會(huì)員。

凱利一生僅出版一本專(zhuān)著，便是1876年的《橢圓函數(shù)初論》，但發(fā)表了近1000篇論文，其中一些影響極為深遠(yuǎn)。凱利在勸說(shuō)劍橋大學(xué)接受女學(xué)生中起了很大作用。他在生前得到了他所處時(shí)代一位科學(xué)家可能得到的幾乎所有重要榮譽(yù)。

Arthur Cayley

這道題有一定難度，在Stack Overflow上也有一些回答，但給出代碼的寥寥無(wú)幾，我們先列幾個(gè)Stack Overflow上的提問(wèn)以及回答吧：

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

上面給的答案就是一種“滾下山”（roll downhill）的方式，首先找到中間行，并在中間行中找到該行的最小值，然后判斷它在該列中是不是局部最小值，如果是的話，那就返回這個(gè)值，否則向該列的小一側(cè)方向移動(dòng)，如此循環(huán)往復(fù)。

Peak Finding

1

題目的介紹：假設(shè)你掉入了一個(gè)群山連綿的地方，很口渴，需要找個(gè)水池，那方法是怎么樣的。（看來(lái)算法真的還是有用處的，可以自救）

2

3

建模：把這個(gè)問(wèn)題歸結(jié)為二維數(shù)組（或矩陣）的找局部最大值問(wèn)題

4

看這個(gè)數(shù)組的中間元素不能拆分這個(gè)問(wèn)題

5

找出這個(gè)矩陣每列的最大值，列出來(lái)

6

如果中間列的最大值不是局部最大值，那么找到它的更大值的鄰居。以此類(lèi)推。這也正是前面我們提到的滾下山”（roll downhill）的方式。

7

算出時(shí)間復(fù)雜度是nlgn，能否更快？

8

9

10

算出復(fù)雜度是n，完美解決！

如上面的圖可知，他們解決的是局部最大值的問(wèn)題，但其實(shí)我們的局部最小值也是一樣的解決方案。
我們的先把滾下山的解法寫(xiě)出來(lái)，因?yà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;
    }

    /**
     * 找出數(shù)組中的最小值的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

但答案要求的是復(fù)雜度為n的解法，我們通過(guò)獲取submatrix的解法實(shí)現(xiàn)：

答案

代碼索引

廣告

我的首款個(gè)人開(kāi)發(fā)的APP壁紙寶貝上線了，歡迎大家下載。