在行列都排好序的矩阵中找数

【题目】 给定一个有N*M的整型矩阵matrix和一个整数K matrix的每一行和每一列都是 排好序的。实现一个函数，判断K是否在matrix中。 例如下图矩阵:如果K为7，返回true；如果K为22，返回false。

【要求】 时间复杂度为O(N M)，额外空间复杂度为O(1)。

实现思路: 这题有个特殊的地方,即矩阵每行每列都是排好序的,特殊的题型决定了可以用比较优秀的算法解决问题.其隐藏条件是每个空的数据都大于左边,小于下边的值. 这题就可以利用这个特性,从右上角入手,小于该点的值只可能存在左边,大于该点的值只可能存在该点下面,如果超出边界则数据必步存在. 这里以右上角开始查找7为例,7大于5肯定在5下面,index标记10.7小于10,肯定存在于index左边,以此规律去查找....

代码:

代码语言：javascript复制

package com.day1.practice;

public class FindNumInSortedMatrix {
    public static boolean isContains(int[][] matrix, int Key) {
        //定义初始索引位置为右上角的点
        int iR=0;
        int iC=matrix[0].length-1;
        int endR=matrix.length;
        int endC=-1;
        while (iR<endR&&iC>endC)
        {
            if (matrix[iR][iC]==Key){
                return true;
            }
            if (Key>matrix[iR][iC]){
                iR  ;
                continue;//这里要加continue,不然可能会继续到下一个if造成数组越界
            }
            if (Key<matrix[iR][iC])
            {
                iC--;
                continue;
            }        }
        return false;
    }

    public static void main(String[] args){
        int[][] matrix = new int[][] { { 0, 1, 2, 3, 4, 5, 6 },// 0
                { 10, 12, 13, 15, 16, 17, 18 },// 1
                { 23, 24, 25, 26, 27, 28, 29 },// 2
                { 44, 45, 46, 47, 48, 49, 50 },// 3
                { 65, 66, 67, 68, 69, 70, 71 },// 4
                { 96, 97, 98, 99, 100, 111, 122 },// 5
                { 166, 176, 186, 187, 190, 195, 200 },// 6
                { 233, 243, 321, 341, 356, 370, 380 } // 7
        };
        int K = 43;
        System.out.println(isContains(matrix, K));
    }
}

matrix

0 人点赞