题目描述

给定一个有N×M的整型矩阵matrix和一个整数K，matrix每行每列都排好序了。
实现一个函数，判断K是否在matrix中。

分析

1. 从右上角的数开始寻找
2. 右上角比k小，说明k不可能在第一行了，看下面的行
3. 右上角比k大，说明k不可能在最后一列，看左边的列

代码实现

public class FindNumInSortMatrix {
    public static int[] find(int[][] matrix, int num) {
        // 1-----------------------------------------------------
        int a = 0;// 行
        int b = matrix[0].length - 1;// 列
        while (a < matrix.length && b > -1) {
            if (matrix[a][b] == num) {
                return new int[] { a, b };
            } else if (matrix[a][b] < num) { // 2-------------------------
                a++;// 往下一行走
            } else { // 3-----------------------------------------------------
                b--;// 往该列左走
            }
        }
        return new int[] { -1, -1 };
    }

    public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
        int num1 = 5;
        int arr1[] = find(matrix, num1);
        System.out.println(num1 + "在" + (arr1[0] + 1) +"行" + (arr1[1] + 1) + "列");
        int num2 = 7;
        int arr2[] = find(matrix, num2);
        System.out.println(num2 + "在" + (arr2[0] + 1) +"行" + (arr2[1] + 1) + "列");
    }
}

测试结果