編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 。該矩陣具有以下特性:
每行的元素從左到右升序排列。
每列的元素從上到下升序排列。
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int rows = matrix.size(); // 行數int cols = matrix[0].size(); // 列數int x=0;int y=cols-1;// 從右上角開始while(x<rows && y>=0){if(matrix[x][y] == target) // 找到,返回return true;else if(matrix[x][y] > target) // 當前值比目標值大,則繼續往左找y--;else if(matrix[x][y] < target) // 當前值比目標值小,則繼續往下找x++;}return false;}
};
時間復雜度O(m+n)