矩阵查数

[编程题]矩阵查数

热度指数：5646 时间限制：C/C++ 4秒，其他语言8秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个二维整型矩阵，已知矩阵的每一行都按照从小到大的顺序排列，每一列也都按照从小到大的顺序排列。现在给出一个数，请写一个函数返回该数是否存在于矩阵中。

矩阵中出现的数字与需要查找的数(k)都为0~100000之间的整数，且矩阵的大小在3000*3000以内。

在保证正确性的基础上，请尽量给出比较高效的解法。请列出你的算法时间复杂度与空间复杂度分别是多少？

输入描述:

输入两个整数m,n, 且 0<m<=3000, 0<n<=3000。

接着输入一个vector<vector<int>> matrix矩阵，大小为m行n列，与一个int k，为需要查找的数字。

输出描述:

输出true或者false，true表示该数k存在于该matrix矩阵中，false表示该数k不存在于该matrix矩阵中。

示例1

输入

输出

true

说明

4位于矩阵的第二行第二列，故输出true

算法知识视频讲解

Java

牛客697326250号

输入有问题，一直编译报错。。。

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[][] array = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n ; j++) {
                array[i][j] = scanner.nextInt();
            }
        }
        int findNum = scanner.nextInt();
        System.out.println(find(array, m / 2, n / 2, findNum));
    }

    private static boolean find(int[][] array, int lm, int cm, int findNum) {
        int i = array[lm][cm];
        if (i == findNum) {
            return true;
        }
        if (i < findNum && lm + 1 < array.length) {
            if (find(array, lm + 1, cm, findNum)) {
                return true;
            }
        }
        if (i < findNum && cm + 1 < array[0].length) {
            if (find(array, lm, cm + 1, findNum)) {
                return true;
            }
        }
        if (i > findNum && lm - 1 > 0) {
            if (find(array, lm - 1, cm, findNum)) {
                return true;
            }
        }
        if (i > findNum && cm - 1 > 0) {
            if (find(array, lm, cm - 1, findNum)) {
                return true;
            }
        }
        return false;
    }

发表于 2024-11-20 11:27:32 回复(0)

Java

京东内推君

利用有序性，从左上角或者右下角开始查找

代码为从左上角

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int row = scanner.nextInt();
        int column = scanner.nextInt();
        int[][] value = new int[row][column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                value[i][j] = scanner.nextInt();
            }
        }
        int aim = scanner.nextInt();

        int curR = 0;
        int curC = column - 1;
        boolean flag = false;
        while (curR >= 0 && curR < row && curC >= 0 && curC < column) {
            if (value[curR][curC] > aim) {
                curC--;
            } else if (value[curR][curC] < aim) {
                curR++;
            } else {
                flag = true;
                break;
            }
        }
        System.out.println(flag);
    }
}

发表于 2020-06-23 20:18:55 回复(0)

Java