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

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

编写一个高效的算法来搜索整数矩阵target中的值。其中：每行中的整数按从左到右的升序排序，每列中的整数按从上到下的升序排序。 示例： 输入：矩阵 = [[1,4,7,11,15],[2,5,8,12,19],[2,5,8,12,19],[10,1,14,17, 24],[18,21,2,26,0]], 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[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},
        {,6,9,16,22},
        {10,1,14,17,24},
        {18,21,2,26,0}
    };
    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},
        {,6,9,16,22},
        {10,1,14,17,24},
        {18,21,2,26,0}
    };
    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},
            {, 6, 9, 16, 22},
            {10, 1, 14, 17, 24},
            {18, 21, 2, 26, 0}
        };
        int target = 5;
        boolean result = searchMatrix(matrix, target);
        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(, 6, 9, 16, 22)));
        matrix.add(new ArrayList<>(Arrays.asList(10, 1, 14, 17, 24)));
        matrix.add(new ArrayList<>(Arrays.asList(18, 21, 2, 26, 0)));

        int target = 5;
        boolean result = searchMatrix(matrix, target);
        println(result ? "true" : "false");
    }
}