題目描述

在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

例子

輸入一個(gè)數(shù)組：

num[ 3 ][ 4 ] = [  
1 , 4 , 6 , 28 ,  
2 , 7 , 32 , 30 ,  
10 , 11 , 67 , 79  
]

需要查找一個(gè)數(shù)字32，則返回 true。

思路以及解答

暴力破解

直接暴力遍歷，但是在最壞的情況是遍歷完所有的元素才能獲取結(jié)果。如果這個(gè)數(shù)組規(guī)模是 n * m，那么時(shí)間復(fù)雜度就是 O(n × m)，沒(méi)有借助其他的空間，空間復(fù)雜度為 O(1)。

比較查找法

但是我們換一種思路，我們選定左下角的10 ( num[2][0], i = 2, j = 0 )作為起點(diǎn)，如果大于10 ,那么 i + 1 ,如果小于 10 ，則 j + 1 ，則下一個(gè)查找的數(shù)字是 11 ,我們知道 32 仍然比 11 大，則往右找到 67 ，繼而 32 比 67 小，我們應(yīng)該往上找，找到了 32 。
如果找 28 ，則是最壞的結(jié)果，查找知道數(shù)組的右上角結(jié)束，這樣一來(lái)，最壞的結(jié)果就是 O（n+m）。

代碼

public class Solution {
    public boolean Find(int target, int[][] array) {
        int size = array.length;
        if (size == 0) return false;
        int length = array[0].length;
        if (length == 0) return false;

        int i = size - 1, j = 0; // 從左下角開(kāi)始
        while (i >= 0 && j < length) {
            if (array[i][j] == target) {
                return true;
            } else if (array[i][j] < target) {
                j++; // 向右移動(dòng)
            } else {
                i--; // 向上移動(dòng)
            }
        }
        return false;
    }
}