luckydog

V1

2022/03/25阅读:30主题:默认主题

Code_240

搜索二维矩阵

code 240
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列
来源:力扣(LeetCode)

分析

  • 每行进行二分查找
  • 双指针 row, col 从右上向左下找

code

public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int m = matrix[0].length;

        for (int[] row : matrix) {
            int index = searchT(row, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }
    private int searchT(int[] row, int target) {
        int left = 0, right = row.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (row[mid] == target) {
                return mid;
            }else if (row[mid] > target) {
                right = mid - 1;
            }else if (row[mid] < target){
                left = mid + 1;
            }
        }
        return -1;
    }
public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int m = matrix[0].length;
        int row = 0;
        int col = m - 1;
        while (row < n && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            }else if (matrix[row][col] < target) {
                row++;
            }else if (matrix[row][col] > target) {
                col--;
            }
        }
        return false;
    }

分类:

后端

标签:

Java

作者介绍

luckydog
V1