二维矩阵搜索问题——小米面试题

迈不过友情╰ 2024-02-19 08:07 25阅读 0赞

## 二维矩阵搜索问题——小米面试题 ##

编写一个高效的算法来搜索整数矩阵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");
        }
    }