前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >在行列都排好序的矩阵中找数

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

作者头像
名字是乱打的
发布2022-05-13 09:53:25
3180
发布2022-05-13 09:53:25
举报
文章被收录于专栏:软件工程

【题目】 给定一个有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));
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-05-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档