二维矩阵搜索问题——小米面试题
编写一个高效的算法来搜索整数矩阵target中的值。其中：每行中的整数按从左到右的升序排序，每列中的整数按从上到下的升序排序。
示例：
输入：矩阵 = [[1,4,7,11,15],[2,5,8,12,19],[2,5,8,12,19],[10,13,14,17, 24],[18,21,23,26,30]],
target = 5
输出: true
算法思路，这个题有两个算法思路，一个是把二维的变成一维的，然后再进行二分查找，时间复杂度是O(nlogn)
另一个方法就是寻找规律，因为这个矩阵是从左到右，从上到下都是递增的，所以可以采用，我们从这个矩阵的右上角开始，如果当前位置的值小于目标值，那么我们向下移动一行；如果当前位置的值大于目标值，那么我们向左移动一列。我们不断重复这一过程，直到找到目标值，或者搜索区域为空，时间复杂度的话为O（m + n）;
- c++
/*采用vector的写法*/ #include<bits/stdc++.h> using namespace std; bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int row = 0; int col = matrix[0].size() - 1; while(row < (int)matrix.size() && col >= 0){ if (matrix[row][col] == target) return true; else if (matrix[row][col] < target) row ++; else col --; } return false; } int main() { vector<vector<int>> 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} }; int target = 5; bool result = searchMatrix(matrix, target); cout << (result ? "true" : "false") << endl; return 0; } /*采用数组的写法*/ #include <iostream> using namespace std; bool searchMatrix(int matrix[5][5], int target, int rows, int cols) { int row = 0; int col = cols - 1; while (row < rows && col >= 0) { if (matrix[row][col] == target) { return true; } else if (matrix[row][col] < target) { row++; } else { col--; } } return false; } int main() { int matrix[5][5] = { {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} }; int target = 5; bool result = searchMatrix(matrix, target, 5, 5); cout << (result ? "true" : "false") << endl; return 0; }
- Java
/*数组版*/ import java.util.*; class Main { public static boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int row = 0; int col = matrix[0].length - 1; while (row < matrix.length && col >= 0) { if (matrix[row][col] == target) { return true; } else if (matrix[row][col] < target) { row++; } else { col--; } } return false; } public static void main(String[] args) { int[][] 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} }; int target = 5; boolean result = searchMatrix(matrix, target); System.out.println(result ? "true" : "false"); } } /*ArrayList版*/ import java.util.*; class Main { public static boolean searchMatrix(ArrayList<ArrayList<Integer>> matrix, int target) { if (matrix == null || matrix.size() == 0 || matrix.get(0).size() == 0) { return false; } int row = 0; int col = matrix.get(0).size() - 1; while (row < matrix.size() && col >= 0) { if (matrix.get(row).get(col) == target) { return true; } else if (matrix.get(row).get(col) < target) { row++; } else { col--; } } return false; } public static void main(String[] args) { ArrayList<ArrayList<Integer>> matrix = new ArrayList<>(); matrix.add(new ArrayList<>(Arrays.asList(1, 4, 7, 11, 15))); matrix.add(new ArrayList<>(Arrays.asList(2, 5, 8, 12, 19))); matrix.add(new ArrayList<>(Arrays.asList(3, 6, 9, 16, 22))); matrix.add(new ArrayList<>(Arrays.asList(10, 13, 14, 17, 24))); matrix.add(new ArrayList<>(Arrays.asList(18, 21, 23, 26, 30))); int target = 5; boolean result = searchMatrix(matrix, target); System.out.println(result ? "true" : "false"); } }
