給你一個滿足下述兩條屬性的 m x n 整數矩陣：
每行中的整數從左到右按非嚴格遞增順序排列。
每行的第一個整數大于前一行的最后一個整數。
給你一個整數 target ，如果 target 在矩陣中，返回 true ；否則，返回 false 。

示例 1：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true

示例 2：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
輸出：false

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
$?10^4$ <= matrix[i][j], target <= $10^4$

---

知識點：
數組、矩陣、二分查找、排除法

---

解1（非常暴力）：
核心思想：定義輔助數組存儲所有元素（因為每一行的第一個元素大于上一行的最后一個元素，因此可以這么操作），然后對這個輔助數組進行二分查找。

時間復雜度：$O(mn)$。
空間復雜度：$O(mn)$。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {//獲取行數、列數int m = matrix.length;int n = matrix[0].length;//定義輔助數組，存儲所有元素int[] nums = new int[m * n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {nums[i * n + j] = matrix[i][j];}}//定義二分查找的指針int low = 0;int high = m * n - 1;//只要兩個指針不重合，就繼續循環while (low <= high) {//獲取中位數int mid = (low + high) / 2;//判斷是否存在if (nums[mid] == target) {return true;} else if (nums[mid] > target) {high = mid - 1;} else {low = mid + 1;}}//未找到return false;}
}

---

解2（排除法）：
核心思想：同 #240. 搜索二維矩陣Ⅱ。

時間復雜度：$O(m+n)$。
空間復雜度：$O(1)$。未使用輔助數組，僅使用int類型的輔助變量。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {//獲取行數、列數int m = matrix.length;int n = matrix[0].length;//從右上角開始找int i = 0;int j = n - 1;//只要還有元素，就繼續循環while (i < m && j >= 0) {//找到元素，返回if (matrix[i][j] == target) {return true;}//若當前元素＞target，則遍歷前面一列else if (matrix[i][j] > target) {j--;}//否則，遍歷下面一行else {i++;}}//此時表明不存在元素return false;}
}

---

解3（二分查找）：
核心思想：在形式上將矩陣所有元素放在一個數組中（因為每一行的第一個元素大于上一行的最后一個元素，因此可以這么操作），在實際上通過matrix[i/n][i%n]獲取mid在matrix中對應的元素，然后使用二分查找

時間復雜度：$O(log(mn))$。
空間復雜度：$O(1)$。未使用輔助數組。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {//獲取行數、列數int m = matrix.length;int n = matrix[0].length;//定義二分查找的指針int low = 0;int high = m * n - 1;//只要兩個指針不重合，就繼續循環while (low <= high) {//獲取中位數int mid = (low + high) / 2;//獲取矩陣對應的mid元素int item = matrix[mid / n][mid % n];//判斷是否存在if (item == target) {return true;} else if (item > target) {high = mid - 1;} else {low = mid + 1;}}//未找到return false;}
}

---

參考：
1、靈神題解