Problem: 240. 搜索二維矩陣 II
編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性：
每行的元素從左到右升序排列。
每列的元素從上到下升序排列。

整體思路

這段代碼旨在解決一個經典的矩陣搜索問題：搜索二維矩陣 II (Search a 2D Matrix II)。問題要求在一個特殊的 M x N 矩陣中高效地查找一個目標值 target。這個矩陣的特殊之處在于：

• 每一行的元素從左到右升序排列。
• 每一列的元素從上到下升序排列。

該算法采用了一種非常巧妙且高效的 “Z”字形（或稱為“鋸齒形”）查找法。它利用了矩陣的行列雙重有序性，以線性的時間復雜度完成搜索。

1. 選擇起點：

   • 算法的關鍵在于選擇一個合適的起點。它選擇了矩陣的 右上角 (0, n-1) 作為起始搜索點。
   • 為什么是右上角（或左下角）：這個位置非常特殊。對于右上角的元素 matrix[i][j]：
     • 它小于同一行右側的所有元素（不存在）。
     • 它大于同一行左側的所有元素。
     • 它小于同一列下方的所有元素。
     • 它大于同一列上方的所有元素（不存在）。
   • 這種特性使得每一次比較都能排除掉一整行或一整列的元素，從而實現高效的搜索。

2. 搜索路徑與排除邏輯：

   • 算法使用一個 while 循環來持續搜索，只要指針 (i, j) 還在矩陣范圍內（i < m && j >= 0）。
   • 在循環的每一步，將當前指針指向的元素 matrix[i][j] 與 target 進行比較：
     • Case 1: matrix[i][j] == target
       • 找到了目標值，直接返回 true。
     • Case 2: matrix[i][j] < target
       • 由于當前元素 matrix[i][j] 比 target 小，并且它已經是當前行 i 中最大的元素（因為我們從最右邊開始），所以 target 不可能在當前行的任何位置。
       • 因此，我們可以安全地排除掉整個第 i 行，并將搜索范圍向下移動一行。實現方式是 i++。
     • Case 3: matrix[i][j] > target
       • 由于當前元素 matrix[i][j] 比 target 大，并且它已經是當前列 j 中最小的元素（因為我們從最上邊開始），所以 target 不可能在當前列的任何位置。
       • 因此，我們可以安全地排除掉整個第 j 列，并將搜索范圍向左移動一列。實現方式是 j--。

3. 終止條件：

   • while 循環會一直持續，直到指針移出矩陣邊界（i 越過下邊界或 j 越過左邊界）。
   • 如果循環結束了還沒有找到 target，就說明目標值在矩陣中不存在，返回 false。

這個算法的路徑就像在矩陣中畫一條從右上到左下的折線，每一步都剔除一行或一列，因此效率非常高。

完整代碼

class Solution {/*** 在一個行列都升序的矩陣中高效地查找一個目標值。* @param matrix 一個 M x N 的整數矩陣，每行從左到右升序，每列從上到下升序。* @param target 要查找的目標值。* @return 如果找到目標值則返回 true，否則返回 false。*/public boolean searchMatrix(int[][] matrix, int target) {// 獲取矩陣的行數和列數int m = matrix.length;int n = matrix[0].length;// 步驟 1: 初始化指針，指向矩陣的右上角int i = 0;     // 行指針，從第 0 行開始int j = n - 1; // 列指針，從最后一列開始// 步驟 2: 循環搜索，只要指針還在矩陣范圍內while (i < m && j >= 0) {// Case 1: 找到目標值if (matrix[i][j] == target) {return true;}// Case 2: 當前元素小于目標值// 說明 target 不可能在當前行，因為 matrix[i][j] 是當前行最大的// 排除當前行，向下移動if (matrix[i][j] < target) {i++;} else { // Case 3: 當前元素大于目標值// 說明 target 不可能在當前列，因為 matrix[i][j] 是當前列最小的// 排除當前列，向左移動j--;}}// 步驟 3: 如果循環結束仍未找到，說明目標值不存在return false;}
}

時空復雜度

時間復雜度：O(M + N)

1. 指針移動分析：
   • 算法的核心是兩個指針 i 和 j 的移動。
   • 指針 i 只會單調遞增（向下移動），從 0 最多移動到 m。
   • 指針 j 只會單調遞減（向左移動），從 n-1 最多移動到 -1。
2. 循環次數：
   • 在 while 循環的每一次迭代中，i 或 j 至少有一個會移動。
   • i 最多移動 M 次，j 最多移動 N 次。
   • 因此，循環的總執行次數最多為 M + N 次。

綜合分析：
算法的時間復雜度與行數和列數的和成線性關系，即 O(M + N)。

空間復雜度：O(1)

1. 主要存儲開銷：該算法直接在輸入的 matrix 數組上進行查找，沒有創建任何新的、與輸入規模 M 或 N 成比例的數據結構。
2. 輔助變量：只使用了 m, n, i, j, target 等幾個常數數量的變量。

綜合分析：
算法所需的額外輔助空間是常數級別的。因此，其空間復雜度為 O(1)。這是一個空間效率極高的原地算法。

參考靈神