我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 面試題04. 二維數組中的查找

題目

在一個 n * m 的二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

示例:

現有矩陣 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
給定 target = 5，返回 true。

給定 target = 20，返回 false。

限制：

• 0 <= n <= 1000

• 0 <= m <= 1000

註意：本題與主站 240 題相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

思路1-二分查找

因為所有的數都是排好序的，那麼我們需要找到中間值，然後採用二分查找；
分析後可以發現右上角的值就是中間位置值，所以可以從此處開始查找；
n為橫，m為豎，查找的邏輯：

• 以右上角到左下角為軸，軸點連接的橫豎的數據可拉直看為一個有序區間；
• 橫坐標代表較小值，豎坐標代表較大值，從右上角[row，col]開始搜索，初始row=0，col=m-1；
  • 若當前值小於目標值，則row++;
  • 若當前值大於目標值，則col--；

演算法複雜度:

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(logn\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年4月28日 下午4:45:26 
 * @Description: 面試題04. 二維數組中的查找
 *
 */
public class LeetCode_Offer_04 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年4月28日 下午5:51:04 
	 * @param: @param matrix
	 * @param: @param target
	 * @param: @return
	 * @return: boolean
	 * @Description: 1-從右上角向左下角把相連的橫豎行拉直就是一個連續的遞增數組；
	 *
	 */
	public boolean findNumberIn2DArray(int[][] matrix, int target) {
		// 特例判斷
		if (matrix == null || matrix.length == 0) {
			return false;
		}
		int m = matrix.length;
		int n = matrix[0].length;
		int row = 0, col = n - 1;
		// 二分查找，以右上角的位置作為中間位置，小於target就row++，否則就col--
		while (row < m && col > -1) {
			if (matrix[row][col] > target) {
				col--;
			} else if (matrix[row][col] < target) {
				row++;
			} else {
				return true;
			}
		}
		// 越界仍為找到時
		return false;
	}
}